forked from szl0072/Leetcode-Solution-Code
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathBalancedBinaryTree.java
53 lines (46 loc) · 1.13 KB
/
BalancedBinaryTree.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package leetcode;
/**
* Project Name : Leetcode
* Package Name : leetcode
* File Name : BalancedBinaryTree
* Creator : Edward
* Date : Aug, 2017
* Description : TODO
*/
public class BalancedBinaryTree {
/**
* 110. Balanced Binary Tree
* Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree
in which the depth of the two subtrees of every node never differ by more than 1.
1 -- 3
/ \
2 3 -- 1
/ \
4 5 -- 1
1
/ \
2 3 2 --> 3 3 --> 1
/ \
4 5 -- 2
\
9 -- 1
time : O(n);
space : O(n);
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return helper(root) != -1;
}
public int helper(TreeNode root) {
if (root == null) return 0;
int l = helper(root.left);
int r = helper(root.right);
if (l == -1 || r == -1 || Math.abs(l - r) > 1) {
return -1;
}
return Math.max(l, r) + 1;
}
}