Java O(n) space, O(n) time complexity


  • 0
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        private int max;
        
        public int[] findMode(TreeNode root) {
            
            HashMap<Integer, Integer> map = new HashMap();
            makeMap(root, map);
            List<Integer> list = new ArrayList();
           
            for(Map.Entry entry : map.entrySet()) {
                if((int)entry.getValue() == max) {
                   list.add((int) entry.getKey()); 
                }
            }
            int retArr[] = new int[list.size()];
            for(int i = 0; i < retArr.length; ++i) {
                retArr[i] = (int)list.get(i);
            }
            return retArr;
               
        }
        
        private void makeMap(TreeNode root, HashMap<Integer, Integer>map) {
            if(root == null) return;
            else {
                if(map.containsKey(root.val)) {
                    max = Math.max(max, map.get(root.val) + 1);
                    map.put(root.val, map.get(root.val) + 1);
                }
                else {
                    max = Math.max(max, 1);
                    map.put(root.val, 1);
                }
                makeMap(root.left, map);
                makeMap(root.right, map);
            }
        }
    }
    

Log in to reply
 

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