forked from gouthampradhan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEqualTreePartition.java
More file actions
95 lines (81 loc) · 1.83 KB
/
EqualTreePartition.java
File metadata and controls
95 lines (81 loc) · 1.83 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package tree;
/**
* Created by gouthamvidyapradhan on 17/02/2018.
* 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:
The range of tree node value is in the range of [-100000, 100000].
1 <= n <= 10000
*/
public class EqualTreePartition {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
private long sum;
private boolean possible = false;
public static void main(String[] args) throws Exception{
}
public boolean checkEqualTree(TreeNode root) {
sum = 0L;
getSum(root);
getDiff(root);
return possible;
}
private void getSum(TreeNode node){
if(node != null){
sum += node.val;
getSum(node.left);
getSum(node.right);
}
}
private Long getDiff(TreeNode node){
if(node == null) return null;
Long left = getDiff(node.left);
Long right = getDiff(node.right);
if(left != null){
if((sum - left) == left){
possible = true;
}
}if(right != null){
if((sum - right) == right){
possible = true;
}
}
Long curr = (long)node.val;
if(left != null){
curr += left;
} if(right != null){
curr += right;
}
return curr;
}
}