LeetCode-110-平衡二叉樹
2022-02-18由 雄獅虎豹 發表于 畜牧業
建構函式何時被呼叫
平衡二叉樹
題目描述：給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 。
示例說明請見LeetCode官網。
連結：https：//leetcode-cn。com/problems/balanced-binary-tree/
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。
解法一：遞迴
首先，新增一個方法height，該方法透過層序遍歷的方式得到二叉樹的高度。
然後，透過遞迴法判斷二叉樹是否是平衡二叉樹，遞迴過程如下：
如果當前根節點為空，則直接返回true；
否則，計算當前根節點的左右子樹的高度，如果當前根節點的左右子樹的高度之差不超過1，則遞迴判斷當前根節點的左右子樹是否是平衡二叉樹；否則，返回false。
import
com。kaesar。leetcode。TreeNode；
import
java。util。LinkedList；
import
java。util。Queue；
public
class
LeetCode_110
{
/**
* 遞迴
*
*
@param
root
*
@return
*/
public
static
boolean
isBalanced
（TreeNode root）
{
// 如果當前根節點為null，肯定是平衡的，直接返回true
if
（root ==
null
） {
return
true
；
}
// 如果當前根節點的左右子樹的高度之差不超過1，則遞迴判斷當前根節點的左右子樹是否是平衡二叉樹
if
（height（root。left） - height（root。right） >= -
1
&& height（root。left） - height（root。right） <=
1
） {
return
isBalanced（root。left） && isBalanced（root。right）；
}
else
{
return
false
；
}
}
/**
* 層序遍歷：透過計算二叉樹的層數來得到二叉樹的高度
*
*
@param
root 當前根節點
*
@return
返回二叉樹的高度
*/
public
static
int
height
（TreeNode root）
{
int
result =
0
；
if
（root ==
null
） {
return
result；
}
Queue
new
LinkedList<>（）；
nodes。add（root）；
result =
0
；
while
（！nodes。isEmpty（）） {
result++；
int
count = nodes。size（）；
while
（count >
0
） {
TreeNode cur = nodes。poll（）；
if
（cur。left ！=
null
） {
nodes。add（cur。left）；
}
if
（cur。right ！=
null
） {
nodes。add（cur。right）；
}
count——；
}
}
return
result；
}
public
static
void
main
（String［］ args）
{
// 測試用例，期望返回結果： true
TreeNode root =
new
TreeNode（
3
）；
root。left =
new
TreeNode（
9
）；
root。right =
new
TreeNode（
20
）；
root。right。left =
new
TreeNode（
15
）；
root。right。right =
new
TreeNode（
7
）；
System。out。println（isBalanced（root））；
}
}
【每日寄語】
把所有的不快給昨天，把所有的希望給明天，把所有的努力給今天。
