Java AC Solution


  • 13

    O(n) time O(n) space

    public class Solution {
        Map<Integer, Integer> map; 
        int max = 0;
        public int[] findMode(TreeNode root) {
            if(root==null) return new int[0]; 
            this.map = new HashMap<>(); 
            
            inorder(root); 
            
            List<Integer> list = new LinkedList<>();
            for(int key: map.keySet()){
                if(map.get(key) == max) list.add(key);
            }
            
            int[] res = new int[list.size()];
            for(int i = 0; i<res.length; i++) res[i] = list.get(i);
            return res; 
        }
        
        private void inorder(TreeNode node){
            if(node.left!=null) inorder(node.left);
            map.put(node.val, map.getOrDefault(node.val, 0)+1);
            max = Math.max(max, map.get(node.val));
            if(node.right!=null) inorder(node.right); 
        }
    }
    

    Just travel the tree and count, find the those with max counts. Nothing much. Spent 10min on figuring out what is mode....

    If using this method (hashmap), inorder/preorder/postorder gives the same result. Because essentially you just travel the entire nodes and count. And BST is not necessary. This method works for any tree.


  • 0
    J

    Did you consider the use of BST? I thought since it's BST, I can just put to map if left child's value is the same as node's, it did save some space but will fail since the tree can be built without duplicates in test case...


  • 2

    It can be done in O(1) without considering the recursive call stack
    beats 100%

    void helper(TreeNode root, int[] var, List<Integer> result){
            if(root == null) return;
            helper(root.left,var,result);
            var[1] = root.val==var[2] ? var[1]+1 : 1;
            if(var[1] >= var[0]){
                if(var[1] > var[0]) result.clear();
                var[0] = var[1];
                if(result.size()==0 || result.get(result.size()-1)!=root.val){
                    result.add(root.val);
                }
            }
            var[2] = root.val;
            helper(root.right,var,result);
        }
        //without extra space
        public int[] findMode(TreeNode root) {
            List<Integer> temp = new LinkedList<>();
            int[] var = new int[3]; // var[0] = max, var[1] = curr_max, var[2] = prev
            helper(root,var,temp);
            
            int[] result = new int[temp.size()];
            for(int i=0;i<result.length;i++) result[i] = temp.get(i);
            return result;
        }
    
    

    For detailed Explanation: https://discuss.leetcode.com/topic/77309/java-o-1-space-solution-beats-100


  • 0

    @qingyun-wu559-gmail-com You can save space by traveling twice, as said by @StefanPochmann.


  • 0

    @Chidong

    Not O(1) space, but smooth and clear.


  • 0
    D

    For this solution, inorder traversal is not important because preorder/postorder can work.


  • 0
    N

    @prateek470 worse case extra space O(n) , no ?


  • 0

    @ndlu01 In the problem, recursive calls are not considered in space complexity.


  • 0
    I

    @prateek470

    but the temp list is in the main stack, so it will always exit and consume space in the worst case..?


  • 1

    Similar idea, I use post order though. Btw, the return value type int[] make our code messy. So I ask help for lambda. Thanks for sharing!

        public int[] findMode(TreeNode root) {
            Map<Integer,Integer> freq = new HashMap<>();
            int max = dfs(root, freq);
            return freq.entrySet().stream().
                    filter(e -> e.getValue() == max).
                    mapToInt(e -> e.getKey()).toArray();
        }
    
        private int dfs(TreeNode root, Map<Integer,Integer> freq) {
            if (root == null) return 0;
            int l = dfs(root.left, freq);
            int r = dfs(root.right, freq);
            freq.put(root.val, freq.getOrDefault(root.val, 0) + 1);
            return Math.max(freq.get(root.val), Math.max(l, r));
        }
    

  • 1

    This is obviously not O(1) space. I don't know why people give so many thumb ups.
    O(n) space makes this question meaningless.


  • 0
    F

    Same idea, but i think it will explore BST property later

    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        int max = 0;
            
        public int[] findMode(TreeNode root) {
            List<Integer> tmp = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            inOrder(root, map);
            // for (Map.Entry s : map.entrySet()) {
            //     if ((int)s.getValue() == max) {
            //         tmp.add((int)s.getKey());
            //     }
            // }
            for (int key : map.keySet()) {
                if (map.get(key) == max) {
                    tmp.add(key);
                }
            }
            
            int[] res = new int[tmp.size()];
            int id = 0;
            for (int num : tmp) {
                res[id++] = num;
            }
            
            return res;
        }
        private void inOrder(TreeNode root, HashMap<Integer, Integer> map) {
            if (root == null) {
                return;
            }
            inOrder(root.left, map);
            map.put(root.val, map.getOrDefault(root.val, 0) + 1);
            int count = map.get(root.val);
            max = Math.max(max, count);
            inOrder(root.right, map);
        }
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.