663.Equal Tree Partition

1-DFS+HashMap

需要对0特殊处理

The following code has the correct result at a special case when the tree is[0,-1,1], which many solutions dismiss. I think this test case should be added.

https://leetcode.com/problems/equal-tree-partition/discuss/106727/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean checkEqualTree(TreeNode root) {
        //Key: sum, Val: how many times it shows
        Map<Integer, Integer> map = new HashMap<>();
        int sum = getSum(root, map);
        if(sum == 0){
            return map.getOrDefault(sum, 0) > 1;
        }
        else{
            return (sum % 2 == 0) && map.getOrDefault(sum / 2, 0) > 0;
        }
    }
    public int getSum(TreeNode root, Map<Integer, Integer> map){
        if(root == null)
            return 0;
        else{
            int sum = root.val + getSum(root.left, map) + getSum(root.right, map);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            return sum;
        }
    }
}