Given the root of a binary tree, return trueif you can partition the tree into two trees with equal sums of values after removing exactly one edge on the original tree.
**Input:** root = [1,2,10,null,null,2,20]
**Output:** false
**Explanation:** You cannot split the tree into two trees with equal sums after removing exactly one edge on the tree.
Constraints:
The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105
ac
/**
* 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) {
if (root == null || root.left == null && root.right == null) return false;
Set<Integer> vals = new HashSet<>();
int sum = root.val + sum(root.left, vals) + sum(root.right, vals); // don't count root, because, root is not a substree
if (sum % 2 != 0) return false;
return vals.contains(sum/2);
}
public int sum(TreeNode node, Set<Integer> vals) {
if (node == null) return 0;
int left = sum(node.left,vals);
int right = sum(node.right, vals);
int res = node.val + left + right;
vals.add(res);
return res;
}
}
/*
1) sum up all value; 2) if meet 1/2 sum, return true; 3) careful: don't count root, because, root is not a substree
*/
