LeetCode 663. 均匀树划分（树形DP）

样例 1:
输入:     
    5
   / \
  10 10
    /  \
   2   3
输出: True
解释: 
    5
   / 
  10
      
和: 15

   10
  /  \
 2    3

和: 15
 

样例 2:
输入:     
    1
   / \
  2  10
    /  \
   2   20
输出: False
解释: 无法通过移除一条树边将这棵树划分成结点之和相等的两棵子树。
 
注释 :
树上结点的权值范围 [-100000, 100000]。
1 <= n <= 10000

class Solution {
	bool found = false;
	int allsum;
public:
    bool checkEqualTree(TreeNode* root) {
    	allsum = sum(root);
        if(allsum&1) return false;//奇数不可分
    	check(root);
    	return found;
    }
    int sum(TreeNode* root)
    {
    	if(!root) return 0;
    	int l = sum(root->left);
    	int r = sum(root->right);
    	return root->val += l+r;
    }
    bool check(TreeNode* root)
    {
    	if(!root) return false;
        if(found) return true;
    	if(root->left && allsum == 2*root->left->val)
    		return found = true;
    	if(root->right && allsum == 2*root->right->val)
    		return found = true;
    	return check(root->left) || check(root->right);
    }
};