資訊專欄INFORMATION COLUMN
摘要：題意判斷一顆二叉樹(shù)是否是平衡二叉樹(shù)，平衡二叉樹(shù)的定義為，每個(gè)節(jié)點(diǎn)的左右子樹(shù)深度相差小于這是和求最大深度的結(jié)合在一起，可以考慮寫個(gè)函數(shù)找到拿到左右子樹(shù)的深度，然后遞歸調(diào)用函數(shù)判斷左右子樹(shù)是否也是平衡的，得到最終的結(jié)果。
LeetCode 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.
題意：
判斷一顆二叉樹(shù)是否是平衡二叉樹(shù)，平衡二叉樹(shù)的定義為，每個(gè)節(jié)點(diǎn)的左右子樹(shù)深度相差小于1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
3
/
9 20
/
15 7
Return true.
Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
1
/
2 2
/
3 3
/
4 4
Return false.
Solution 1：
這是和求最大深度的結(jié)合在一起，可以考慮寫個(gè)helper函數(shù)找到拿到左右子樹(shù)的深度，然后遞歸調(diào)用isBalanced函數(shù)判斷左右子樹(shù)是否也是平衡的，得到最終的結(jié)果。時(shí)間復(fù)雜度O(n^2)
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftDep = depthHelper(root.left);
int rightDep = depthHelper(root.right);
if (Math.abs(leftDep - rightDep) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
return true;
}
return false;
}
private int depthHelper(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(depthHelper(root.left), depthHelper(root.right)) + 1;
}
Solution 2：
解題思路：
再來(lái)看個(gè)O(n)的遞歸解法，相比上面的方法要更巧妙。二叉樹(shù)的深度如果左右相差大于1，則我們?cè)谶f歸的helper函數(shù)中直接return -1，那么我們?cè)谶f歸的過(guò)程中得到左子樹(shù)的深度，如果=-1，就說(shuō)明二叉樹(shù)不平衡，也得到右子樹(shù)的深度，如果=-1，也說(shuō)明不平衡，如果左右子樹(shù)之差大于1，返回-1，如果都是valid，則每層都以最深的子樹(shù)深度+1返回深度。
public boolean isBalanced(TreeNode root) {
return dfsHeight(root) != -1;
}
//helper function, get the height
public int dfsHeight(TreeNode root){
if (root == null) {
return 0;
}
int leftHeight = dfsHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = dfsHeight(root.right);
if (rightHeight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/71795.html
摘要：在遞歸中，從葉子結(jié)點(diǎn)開(kāi)始一層層返回高度，葉子結(jié)點(diǎn)是。我們返回代表非平衡，返回自然數(shù)代表有效的子樹(shù)高度。 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...
摘要：根據(jù)二叉平衡樹(shù)的定義，我們先寫一個(gè)求二叉樹(shù)最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹(shù)的差值來(lái)判斷當(dāng)前結(jié)點(diǎn)的平衡性，如果不滿足則返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
閱讀 2013·2023-04-26 01:44
閱讀 1339·2021-11-12 10:34
閱讀 1695·2021-09-09 09:33
閱讀 1816·2019-08-30 15:44
閱讀 2959·2019-08-30 13:49
閱讀 2268·2019-08-29 15:26
閱讀 1004·2019-08-26 13:30
閱讀 1484·2019-08-23 18:15
