每日一道 LeetCode (25)：平衡二叉樹(shù)
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)
題目來(lái)源：https://leetcode-cn.com/problems/balanced-binary-tree/
給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。
本題中，一棵高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 。
示例 1:
給定二叉樹(shù) [3,9,20,null,null,15,7]
????3
???/?\
??9??20
????/??\
???15???7
返回 true 。
示例 2:
給定二叉樹(shù) [1,2,2,3,3,null,null,4,4]
???????1
??????/?\
?????2???2
????/?\
???3???3
??/?\
?4???4
返回?false 。
解題思路
這道題題目上已經(jīng)給的很清晰了，要我們判斷一個(gè)樹(shù)是否是一個(gè)高度平衡二叉樹(shù)，而高度平衡二叉樹(shù)的定義是每個(gè)節(jié)點(diǎn)的兩個(gè)子樹(shù)高度差的絕對(duì)值不超過(guò) 1 。
看到這道題不知道各位有啥想法，我的想法就比較粗暴了，前面我記得有好幾道題都介紹過(guò)怎么求一個(gè)二叉樹(shù)的高度，我只需要遍歷這個(gè)樹(shù)上的每一個(gè)節(jié)點(diǎn)，然后分別獲取這個(gè)節(jié)點(diǎn)的左右子樹(shù)高度，看看差的絕對(duì)值有沒(méi)有超過(guò) 1 。
獲取一個(gè)二叉樹(shù)高度有兩種方案，一種是遞歸，一種是迭代。
希望這個(gè)你們都還記得，遞歸拋開(kāi)不聊，迭代的思路是把這個(gè)二叉樹(shù)扔到一個(gè)隊(duì)列里面做循環(huán)，然后算出來(lái)高度。
記不清楚的同學(xué)可以返回去看看第 22 天的文章，求一個(gè)二叉樹(shù)的最大深度。
「每日一道 LeetCode (22)：二叉樹(shù)的最大深度」
這篇文章實(shí)際上使用的是一個(gè)自頂向下的遍歷方案，我看了今天這道題的答案，發(fā)現(xiàn)還能自底向上（果然每個(gè)答案的思路都會(huì)非常的清奇，這就是每天背答案的價(jià)值）。
解題方案一：自頂向下遞歸
首先定義一個(gè)求子樹(shù)高度的 height() 方法，有了這個(gè)方法以后，我們從根節(jié)點(diǎn)開(kāi)始遞歸整個(gè)二叉樹(shù)的左右子節(jié)點(diǎn)，并且判斷左右子節(jié)點(diǎn)的差的絕對(duì)值是否小于 1 。
//?自頂向下遞歸
public?boolean?isBalanced(TreeNode?root)?{
????if?(root?==?null)?return?true;
????else?return?Math.abs(height(root.left)?-?height(root.right))?<=?1?&&?isBalanced(root.left)?&&?isBalanced(root.right);
}
public?int?height(TreeNode?root)?{
????if?(root?==?null)?return?0;
????else?return?Math.max(height(root.left),?height(root.right))?+?1;
}
解題方案二：自底向上遞歸
上面的這種自頂向下的遞歸方案雖然可以求出最后的結(jié)果，但是我們?cè)谇竽骋粋€(gè)節(jié)點(diǎn)的高度的時(shí)候， height() 方法會(huì)被多次調(diào)用，無(wú)形之中增加了時(shí)間復(fù)雜度。
官方的題解中從而給出了一個(gè)很新奇的解法，從底向上遞歸。
在這種解法中，先遞歸的判斷其左右子樹(shù)是否平衡，再判斷已當(dāng)前節(jié)點(diǎn)為根的子樹(shù)是否平衡，如果是平衡的，則返回其高度，如果不平衡，則返回 -1 。
如果有一個(gè)子樹(shù)不平衡，那么整個(gè)子樹(shù)必定不平衡，這種方案無(wú)需遍歷所有的節(jié)點(diǎn)，只要遇到不平衡的子樹(shù)直接返回，只有在最差的情況下會(huì)遍歷二叉樹(shù)中的所有節(jié)點(diǎn)，這時(shí)的時(shí)間復(fù)雜度是 O(n) 。
//?自底向上遞歸
public?boolean?isBalanced_1(TreeNode?root)?{
????return?height_1(root)?>=?0;
}
public?int?height_1(TreeNode?root)?{
????if?(root?==?null)?return?0;
????int?leftHeight?=?height_1(root.left);
????int?rightHeight?=?height_1(root.right);
????if?(leftHeight?==?-1?||?rightHeight?==?-1?||?Math.abs(leftHeight?-?rightHeight)?>?1)?{
????????return?-1;
????}?else?{
????????return?Math.max(leftHeight,?rightHeight)?+?1;
????}
}
