663.md

663. Equal Tree Partition

Description

Given a binary tree with n nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.

Example 1:

Input:     
    5
   / \
  10 10
    /  \
   2   3

Output: True
Explanation: 
    5
   / 
  10
      
Sum: 15

   10
  /  \
 2    3

Sum: 15

Example 2:

Input:     
    1
   / \
  2  10
    /  \
   2   20

Output: False
Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.

Note:

1. The range of tree node value is in the range of [-100000, 100000].
2. 1 <= n <= 10000

Thinking Process

1. Use a hashmap to store sums of each subtree
2. Search through the map to see if there is a subtree with sum half of the total sum

Code

class Solution {
    public boolean checkEqualTree(TreeNode root) {
        Map<TreeNode, Integer> map = new HashMap<>();
        int total = sum(root, map);
        if(total % 2 == 1){
            return false;
        }
        for(TreeNode node:map.keySet()){
            if(map.get(node) * 2 == total && node != root)
                return true;
        }
        return false;
    }
    
    int sum(TreeNode root, Map<TreeNode, Integer> map){
        if(root == null){
            return 0;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        int sumAtRoot = root.val + sum(root.left, map) + sum(root.right, map);
        map.put(root, sumAtRoot);
        return sumAtRoot;
    }
}

Complexity

1. Compute the sum takes O(n), overall time complexity is O(n)
2. Space complexity is O(n) for the hashmap