-
Notifications
You must be signed in to change notification settings - Fork 1
/
Balanced_110.java
33 lines (32 loc) · 1.03 KB
/
Balanced_110.java
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
public class Balanced_110 {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean isBalanced(TreeNode root) {
// Most voted solution #2, time O(n)
return isBalancedHelper(root) != -1;
// My first solution, same as most voted solution #1, time O(n^2)
/*
if (root == null)
return true;
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(getDepth(root.left) - getDepth(root.right)) < 2;
*/
}
private int getDepth(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(getDepth(root.left), getDepth(root.right));
}
private int isBalancedHelper(TreeNode root) {
if (root == null)
return 0;
int l = isBalancedHelper(root.left);
int r = isBalancedHelper(root.right);
if (l == -1 || r == -1 || Math.abs(l-r) > 1)
return -1;
return 1 + Math.max(l,r);
}
}