Java easy to understand (two pass)


  • 0
    R
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        HashSet<Integer> result=new HashSet<>();
        int max=0;
        public int postordercount(TreeNode root){
            if(root==null) return 0;
            else{
                int left=postordercount(root.left);
                int right=postordercount(root.right);
                int num=root.val+left+right;
                if(map.containsKey(num)) map.put(num,map.get(num)+1);
                else map.put(num,1);
                return num;
            }
        }
        public int postorderans(TreeNode root){
            if(root==null) return 0;
            else{
                int left=postorderans(root.left);
                int right=postorderans(root.right);
                int num=root.val+left+right;
                if(map.get(num)>max){
                    result.clear();
                    result.add(num);
                    max=map.get(num);
                }
                else if(map.get(num)==max) result.add(num);
                return num;
            }
        }
        public int[] findFrequentTreeSum(TreeNode root) {
            postordercount(root);
            postorderans(root);
             int[] ret = new int[result.size()];
            Iterator<Integer> iterator = result.iterator();
            for (int i = 0; i < ret.length; i++)
            {
                ret[i] = iterator.next().intValue();
            }
            return ret;
        }
    }
    

  • 0
    R

    Just write this verbose solution without any optimization. Its good for understanding the basic idea of two pass, but it bad for a good solution should be.
    The second pass can be optimized by keeping track of the max count of the tree node value through the first pass.


Log in to reply
 

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