LeetCode 508. 出现次数最多的子树元素和

508. 出现次数最多的子树元素和

 

【DFS】DFS的过程中用map记录子树和已经出现次数，遍历map找出现次数最多即可。

/**
 * 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 {

    // 12:47 6

    public Map<Integer, Integer> map;

    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        int sum = root.val + left + right;
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        return sum;
    }

    public int[] findFrequentTreeSum(TreeNode root) {
        map = new HashMap();
        dfs(root);
        int max = 0;
        List<Integer> list = new ArrayList();
        for(var k: map.keySet()){
            if(map.get(k) > max){
                list.clear();
                list.add(k);
                max = map.get(k);
            }else if(map.get(k) == max){
                list.add(k);
            }
        }
        int[] ans = new int[list.size()];
        int i = 0;
        for(var j: list) ans[i++] = j;
        return ans;
    }
}