FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
LeetCode/src/main/java/L0110_BalancedBinaryTree.java at master · LjyYano/LeetCode · GitHub
LjyYano
/
LeetCode
Public
Notifications
You must be signed in to change notification settings
Fork
125
Star
342
Code
Issues
0
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
LeetCode
/
src
/
main
/
java
/
L0110_BalancedBinaryTree.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
119 lines (105 loc) · 3.64 KB
Breadcrumbs
LeetCode
/
src
/
main
/
java
/
L0110_BalancedBinaryTree.java
Copy path
File metadata and controls
119 lines (105 loc) · 3.64 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
* https://leetcode.cn/problems/balanced-binary-tree/
*
* 给定一个二叉树，判断它是否是高度平衡的二叉树。
* 本题中，一个高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
*
* 示例 1：
* 
* 输入：root = [3,9,20,null,null,15,7]
* 输出：true
*
* 示例 2：
* 
* 输入：root = [1,2,2,3,3,null,null,4,4]
* 输出：false
*
* 示例 3：
* 输入：root = []
* 输出：true
*
* 提示：
* - 树中的节点数在范围 [0, 5000] 内
* - -10⁴ <= Node.val <= 10⁴
*/
public
class
L0110_BalancedBinaryTree
{
public
static
class
TreeNode
{
int
val
;
TreeNode
left
;
TreeNode
right
;
TreeNode
() {}
TreeNode
(
int
val
) {
this
.
val
=
val
;
}
TreeNode
(
int
val
,
TreeNode
left
,
TreeNode
right
) {
this
.
val
=
val
;
this
.
left
=
left
;
this
.
right
=
right
;
}
}
public
boolean
isBalanced
(
TreeNode
root
) {
// 空树也是平衡二叉树
if
(
root
==
null
) {
return
true
;
}
// 计算高度，如果返回 -1 表示不平衡
return
getHeight
(
root
) != -
1
;
}
/**
* 获取树的高度，如果不平衡返回 -1
* 采用自底向上的递归，避免重复计算高度
*/
private
int
getHeight
(
TreeNode
node
) {
// 空节点高度为 0
if
(
node
==
null
) {
return
0
;
}
// 递归计算左子树高度
int
leftHeight
=
getHeight
(
node
.
left
);
// 如果左子树不平衡，直接返回 -1
if
(
leftHeight
== -
1
) {
return
-
1
;
}
// 递归计算右子树高度
int
rightHeight
=
getHeight
(
node
.
right
);
// 如果右子树不平衡，直接返回 -1
if
(
rightHeight
== -
1
) {
return
-
1
;
}
// 如果左右子树高度差大于 1，返回 -1 表示不平衡
if
(
Math
.
abs
(
leftHeight
-
rightHeight
) >
1
) {
return
-
1
;
}
// 返回当前节点的高度
return
Math
.
max
(
leftHeight
,
rightHeight
) +
1
;
}
public
static
void
main
(
String
[]
args
) {
L0110_BalancedBinaryTree
solution
=
new
L0110_BalancedBinaryTree
();
// 测试用例 1：平衡二叉树
TreeNode
root1
=
new
TreeNode
(
3
);
root1
.
left
=
new
TreeNode
(
9
);
root1
.
right
=
new
TreeNode
(
20
);
root1
.
right
.
left
=
new
TreeNode
(
15
);
root1
.
right
.
right
=
new
TreeNode
(
7
);
System
.
out
.
println
(
"测试用例 1："
);
System
.
out
.
println
(
"输入：[3,9,20,null,null,15,7]"
);
System
.
out
.
println
(
"输出："
+
solution
.
isBalanced
(
root1
));
System
.
out
.
println
();
// 测试用例 2：不平衡二叉树
TreeNode
root2
=
new
TreeNode
(
1
);
root2
.
left
=
new
TreeNode
(
2
);
root2
.
right
=
new
TreeNode
(
2
);
root2
.
left
.
left
=
new
TreeNode
(
3
);
root2
.
left
.
right
=
new
TreeNode
(
3
);
root2
.
left
.
left
.
left
=
new
TreeNode
(
4
);
root2
.
left
.
left
.
right
=
new
TreeNode
(
4
);
System
.
out
.
println
(
"测试用例 2："
);
System
.
out
.
println
(
"输入：[1,2,2,3,3,null,null,4,4]"
);
System
.
out
.
println
(
"输出："
+
solution
.
isBalanced
(
root2
));
System
.
out
.
println
();
// 测试用例 3：空树
System
.
out
.
println
(
"测试用例 3："
);
System
.
out
.
println
(
"输入：[]"
);
System
.
out
.
println
(
"输出："
+
solution
.
isBalanced
(
null
));
}
}
Back
|
FazBrowse Home
|
New Git URL