# Java solution, Tree traversal and Sum

• ``````class Solution {
boolean equal = false;
long total = 0;

public boolean checkEqualTree(TreeNode root) {
if (root.left == null && root.right == null) return false;
total = getTotal(root);
checkEqual(root);
return equal;
}

private long getTotal(TreeNode root) {
if (root == null) return 0;
return getTotal(root.left) + getTotal(root.right) + root.val;
}

private long checkEqual(TreeNode root) {
if (root == null || equal) return 0;

long curSum = checkEqual(root.left) + checkEqual(root.right) + root.val;
if (total - curSum == curSum) {
equal = true;
return 0;
}
return curSum;
}
}
``````

• C++ solution. Same idea but a different approach. I store the subtree sum at each node while calculating the total sum to avoid checking the entire subtree later.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool checkEqualTree(TreeNode* root) {
if (!root->left && !root->right) return false;
int sum = sumTree(root);
return checkEqual(root, sum);
}

bool checkEqual(TreeNode* root, int sum){
if (!root) return false;
if (sum-2*root->val==0)
return true;

return checkEqual(root->left, sum) || checkEqual(root->right, sum);
}

int sumTree(TreeNode* root){
if (!root) return 0;
root->val += sumTree(root->left) + sumTree(root->right);
return root->val;
}
};
``````

• This post is deleted!

• Iterative version. DFS. Same idea.

``````class Solution {
public boolean checkEqualTree(TreeNode root) {
if(root == null) return false;
int sum = sumTree(root);
Stack<TreeNode> stk = new Stack<TreeNode>();
stk.push(root);
while(!stk.isEmpty()){
TreeNode node = stk.pop();
if(node.left != null) {
int leftVal = sumTree(node.left);
if(leftVal == sum - leftVal) return true;
stk.push(node.left);
}
if(node.right != null) {
int rightVal = sumTree(node.right);
if(rightVal == sum - rightVal) return true;
stk.push(node.right);
}
}
return false;
}
private int sumTree(TreeNode root){
if(root == null) return 0;
int res = root.val + sumTree(root.left) + sumTree(root.right);
return res;
}
}
``````

• Same thing I did. You can eliminate the cases at the beginning just buy checking whether the `total` is odd.
Since it is impossible to have equal partitions in that case.

• @shawngao I had a very similar approach and it seems like our solution failed the test case [0,1,-1]. Note the fix in the comment.

``````class Solution {
boolean res = false;
TreeNode head;    // Original root of the tree

public boolean checkEqualTree(TreeNode root) {
if (root == null || (root.left == null && root.right == null))   return false;
int sum = sum(root);
if (sum % 2 != 0)   return false;

helper(root, sum / 2);

return res;
}

int helper(TreeNode root, int target) {
if (root == null || res)   return 0;

int left = helper(root.left, target);
int right = helper(root.right, target);

if (root != head &&     // FIX: Check if current root is original root of tree
root.val + left + right == target) {
res = true;
return 0;
}
return root.val + left + right;
}

public int sum(TreeNode root) {
if (root == null)   return 0;
return root.val + sum(root.left) + sum(root.right);
}
}
``````

• ``````boolean result = false;
public boolean checkEqualTree(TreeNode root) {
long sum = total(root, 0);
if(sum % 2 != 0) return false;

result = false;
total(root, sum);
return result;
}
private long total(TreeNode root, long sum) {
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
long left = total(root.left, sum);
long right = total(root.right, sum);
if((root.left!= null && left == sum/2) || (root.right != null && right == sum/2)) {
result = true;
}
return root.val + left + right;
}``````

• @shawngao This solution is failed for case [0, -1, 1].

• @Darrenli yes, this solution failed for case [0,-1,1], and failed [1, -1] as well

``````0                  1
``````

-1 1 -1

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.