LeetCode - 508. 出现次数最多的子树元素和 (二叉树的遍历)

二叉数的先序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    private int maxfreq;
    private Map<Integer,Integer> count;
    private List<Integer> ans;
    public int sumTree(TreeNode root){
    
        int sum = 0;
        if(root == null)
           return 0;
        else{
    
           sum += root.val;
           sum += sumTree(root.left);
           sum += sumTree(root.right);
           count.put(sum,count.getOrDefault(sum,0)+1);
           if(count.getOrDefault(sum,0).compareTo(maxfreq)>0)
           {
    
               maxfreq = count.getOrDefault(sum,0);
               ans = new ArrayList<>();
               ans.add(sum);
           }
           else if(count.getOrDefault(sum,0).compareTo(maxfreq) == 0){
    
               ans.add(sum);
           }
           return sum;
        }
    }
    public int[] findFrequentTreeSum(TreeNode root) {
    
        maxfreq = 0;
        count = new HashMap<>();
        ans = new ArrayList<>();
        sumTree(root);
        int[] ansArray = new int[ans.size()];
        int index = 0;
        for(int i =0 ; i< ansArray.length;i++)
           ansArray[index++] = ans.get(i);
        return ansArray;
    }
}