LeetCode 508. The most frequent subtree elements and

508. The most frequent sub tree elements and

 

【DFS】DFS Used in the process of map Record the subtree and the number of occurrences , Traverse map Find the most frequent occurrences .

/**
 * 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;
    }
}