Equal Tree Partition 07/27

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.

1. The range of tree node value is in the range of [-100000, 100000].

2. 1 <= n <= 10000

Have you met this question in a real interview? Yes

Example

Given     
    5
   / \
  10 10
    /  \
   2   3

return True
Explanation: 
    5
   / 
  10
      
Sum: 15

   10
  /  \
 2    3

Sum: 15

Given   
    1
   / \
  2  10
    /  \
   2   20

return False

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

先更新每个node的值，更新为他两个子节点和他本身的和，那么root节点就是所有点加上他自己的和，如果一个树可以被分为两个和相等的树，那么root节点的值肯定为偶数，并且可以分割的地方的子节点的值必然是root节点的一半。 这个题的坑在于，更新完二叉树的值后，root节点是0，那么0/2还是0，解决办法是跳过root节点，直接递归root的左节点和右节点，寻找里面是否有和root/2的值一样的节点，有的话返回true

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: a TreeNode
     * @return: return a boolean
     */
     
    public boolean equal = false;
    public boolean checkEqualTree(TreeNode root) {
        // write your code here
        
        int topVal = helper(root);
        
        if(topVal %2 == 0){
            return check(root.left,topVal/2) || check(root.right, topVal/2);
        }
        
        return false;
    }
  
    public boolean check(TreeNode root,int target){
        if(root == null){
            return false;
        }
        
        if(target == root.val){
            return true;
        }
        
        return check(root.left,target) ||  check(root.right,target);
        
        
    }
    public int helper(TreeNode root){
        if(root == null){
            return 0;
        }
        
        int leftSum = helper(root.left);
        int rightSum = helper(root.right);
        
        
        
        root.val = root.val+leftSum+rightSum;
        
        return root.val;
        
    }
}