You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/main/java/com/fishercoder/solutions/_110.java
+30-4Lines changed: 30 additions & 4 deletions
Original file line number
Diff line number
Diff line change
@@ -3,13 +3,39 @@
3
3
importcom.fishercoder.common.classes.TreeNode;
4
4
5
5
/**
6
+
* 110. Balanced Binary Tree
7
+
*
6
8
* Given a binary tree, determine if it is height-balanced.
9
+
* 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.
7
10
8
-
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.*/
11
+
Example 1:
12
+
Given the following tree [3,9,20,null,null,15,7]:
13
+
14
+
3
15
+
/ \
16
+
9 20
17
+
/ \
18
+
15 7
19
+
20
+
Return true.
21
+
22
+
Example 2:
23
+
Given the following tree [1,2,2,3,3,null,null,4,4]:
24
+
25
+
1
26
+
/ \
27
+
2 2
28
+
/ \
29
+
3 3
30
+
/ \
31
+
4 4
32
+
33
+
Return false.
34
+
*/
9
35
10
36
publicclass_110 {
11
37
12
-
classSolution1 {
38
+
publicstaticclassSolution1 {
13
39
//recursively get the height of each subtree of each node, compare their difference, if greater than 1, then return false
14
40
//although this is working, but it's not efficient, since it repeatedly computes the heights of each node every time
15
41
//Its time complexity is O(n^2).
@@ -34,7 +60,7 @@ private int getH(TreeNode root) {
34
60
}
35
61
}
36
62
37
-
classSolution2 {
63
+
publicstaticclassSolution2 {
38
64
39
65
publicbooleanisBalanced(TreeNoderoot) {
40
66
returngetH(root) != -1;
@@ -59,4 +85,4 @@ private int getH(TreeNode root) {