[LeetCode] Equal Tree Partition

663. Equal Tree Partition

Given the root of a binary tree, return true if you can partition the tree into two trees with equal sums of values after removing exactly one edge on the original tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
bool res = false;
int dfs(TreeNode* node) {
if(!node) return 0;
return node->val + dfs(node->left) + dfs(node->right);
}
int dfs2(TreeNode* node, int& total) {
if(!node) return 0;
int sum = node->val + dfs2(node->left, total) + dfs2(node->right, total);
if(sum * 2 == total) res = true;
return sum;
}
public:
bool checkEqualTree(TreeNode* root) {
int total = dfs(root);
dfs2(root->left, total);
dfs2(root->right, total);
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/09/PS/LeetCode/equal-tree-partition/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.