# 663. Equal Tree Partition

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

``````class Solution {
public:
bool checkEqualTree(TreeNode* root) {
unordered_map<int, int> m;
int sum = helper(root, m);
if (sum == 0) return m[0] > 1;
return (sum % 2 == 0) && m.count(sum / 2);
}
int helper(TreeNode* node, unordered_map<int, int>& m) {
if (!node) return 0;
int cur = node->val + helper(node->left, m) + helper(node->right, m);
++m[cur];
return cur;
}
};
``````

``````class Solution {
public:
bool checkEqualTree(TreeNode* root) {
stack<int> st;
int sum = helper(root, st);
st.pop();
if (sum % 2 != 0) return false;
while (!st.empty()) {
if (st.top() == sum / 2) return true;
st.pop();
}
return false;
}
int helper(TreeNode* node, stack<int>& st) {
if (!node) return 0;
st.push(helper(node->left, st) + helper(node->right, st) + node->val);
return st.top();
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/663

https://leetcode.com/problems/equal-tree-partition/

https://leetcode.com/problems/equal-tree-partition/discuss/149437/Logical-Thinking-with-Java-Code-Beats-97.25

https://leetcode.com/problems/equal-tree-partition/discuss/106727/JavaC%2B%2B-Simple-solution-with-only-one-HashMaplessgreater.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation