Most Frequent Subtree Sum

https://leetcode.com/problems/most-frequent-subtree-sum/description/

Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Thoughts

既然是统计sum出现的频率，那用一个map记下来即可。 二叉树算sum先想分治，没什么特别的。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, Integer> sums = new HashMap<>();

    private int sum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftSum = sum(node.left);
        int rightSum = sum(node.right);
        int sum = leftSum + rightSum + node.val;
        if (!sums.keySet().contains(sum)) {
            sums.put(sum, 1);
        } else {
            sums.put(sum, sums.get(sum) + 1);
        }

        return sum;
    }


    public int[] findFrequentTreeSum(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        sum(root);
        int maxFreq = 0;
        for (Integer subsum : sums.keySet()) {
            int freq = sums.get(subsum);
            if (freq > maxFreq) {
                res.clear();
                maxFreq = freq;
            }
            if (freq == maxFreq) {
                res.add(subsum);
            }
        }

        int[] results = new int[res.size()];
        for (int i = 0; i < results.length; i++) {
            results[i] = res.get(i);
        }

        return results;
    }
}

Analysis

Errors:

1. int sum = leftSum + rightSum + node.val 忘了加node.val

分治遍历一次, O(n)

Ver.2

改写成iterative版并用maxCount计数避免使用额外的linked list

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> freqs = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> sums = new Stack<>();
        TreeNode cur = root, pre = null;
        int preSum = 0, maxFreq = 0, maxCount = 0;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                sums.push(cur.val);
                cur = cur.left;
            }
            TreeNode node = stack.peek();
            sums.push(sums.pop() + preSum);
            if (node.right != null && node.right != pre) {
                preSum = 0;
                cur = node.right;
                continue;
            }
            pre = stack.pop();
            preSum = sums.pop();
            int freq = freqs.getOrDefault(preSum, 0) + 1;
            freqs.put(preSum, freq);
            if (freq > maxFreq) {
                maxCount = 1;
                maxFreq = freq;
            } else if (freq == maxFreq) {
                maxCount++;
            }
        }

        int[] res = new int[maxCount];
        int i = 0;
        for (Integer subsum : freqs.keySet()) {
            int freq = freqs.get(subsum);
            if (freq == maxFreq) {
                res[i++] = subsum;
            }
        }

        return res;
    }
}