1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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 {
    public boolean checkEqualTree(TreeNode root) {
        Map<Integer, Integer> sumCount = new HashMap<>();
        int treeSum = dfs(root, sumCount);
        if (treeSum % 2 != 0)
            return false;
        int targetSumCount = sumCount.getOrDefault(treeSum / 2, 0);
        return targetSumCount >= 2 || (targetSumCount == 1 && treeSum != 0);
    }

    private int dfs(TreeNode node, Map<Integer, Integer> sumCount) {
        if (node == null)
            return 0;
        int sum = node.val + dfs(node.left, sumCount) + dfs(node.right, sumCount);
        sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
        return sum;
    }
}

统计每一个subtree的sum是多少. 然后看totalSum是否能被2整除, 如果不行, 返回false. 如果可以, 看最后总和的一半出现的次数, 如果大于等于2, 那么返回true, 如果等于1且totalSum不等于总和的一半(cover 0, -1, 1这个edge case), 那么也可以.

时间复杂度: O(n)
空间复杂度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean checkEqualTree(TreeNode root) {
        List<Integer> subtreeSumList = new ArrayList<>();
        int totalSum = dfs(root, subtreeSumList);
        if (totalSum % 2 != 0)
            return false;
        subtreeSumList.remove(subtreeSumList.size() - 1);
        return subtreeSumList.contains(totalSum / 2);
    }

    private int dfs(TreeNode node, List<Integer> subtreeSumList) {
        if (node == null)
            return 0;
        int currSum = node.val + dfs(node.left, subtreeSumList) + dfs(node.right, subtreeSumList);
        subtreeSumList.add(currSum);
        return currSum;
    }
}

记录每一个subtree的sum. 首先还是看totalSum是否能被2整除, 如果不行, 返回false. 如果可以, 我们需要把totalSum首先从list中移除. 然后看list中是否有包含totalSum / 2这个值, 包含就返回true, 否则就是false. 这个remove很关键. 因为root不可能成为partition后的一个candidate.

时间复杂度和空间复杂度不变.