1. 題目

描述

輸入一棵節點數為 n 的二叉樹，判斷該二叉樹是否是平衡二叉樹。

在這里，我們只需要考慮其平衡性，不需要考慮其是不是排序二叉樹

平衡二叉樹（Balanced Binary Tree），具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

樣例解釋：

樣例二叉樹如圖，為一顆平衡二叉樹

注：我們約定空樹是平衡二叉樹。

數據范圍：n≤100,樹上節點的val值滿足 0 ≤n≤1000

要求：空間復雜度O(1)，時間復雜度 O(n)

輸入描述：

輸入一棵二叉樹的根節點

返回值描述：

輸出一個布爾類型的值

示例1

輸入：

{1,2,3,4,5,6,7}

返回值：

true

示例2

輸入：

{}

返回值：

true

2. 解題思路

先來看平衡二叉樹的性質：

平衡二叉樹（Balanced Binary Tree），具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

因此可以借助二叉樹的高度來判斷是否為平衡二叉樹。整體思路為：先計算左右子樹的高度，再比較左右子樹的高度差（如果高度差大于1，則不是平衡二叉樹）。

①對每一個節點的左右子樹進行比較；②如果左子樹不是平衡二叉樹，就沒有必要對右子樹進行是否平衡的判斷；③采用遞歸的方式對左右子樹進行判斷。

由于要采用遞歸來實現平衡二叉樹的判斷，因此需要驗證是否滿足遞歸的兩個條件：

可以看出，求解二叉樹平衡性的判斷滿足遞歸的兩個條件，因此可以采用遞歸的方法來求解。由于平衡性的判斷依賴于二叉樹的高度，二叉樹的高度求解參考前序文章《可視化圖解算法25：二叉樹的最大深度（高度）》，二叉樹高度求解對應的遞推公式如下：

接下來就可以依據二叉樹的高度進行平衡性的判斷，先求解二叉樹的左右子樹的高度，再判斷左右子樹高度差是否超過1，如果超過1則不是平衡二叉樹。

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

• Python編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372113

• Java編碼：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1367352

• Golang編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364777

3. 編碼實現

核心代碼如下：

/**
* 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
*
*
* @param pRoot TreeNode類* @return bool布爾型
*/
func IsBalanced_Solution(pRoot *TreeNode) bool {// write code heretreeDepth(pRoot)return isBalanced
}var isBalanced = truefunc treeDepth(root *TreeNode) int {// 2. 遞歸終止條件if root == nil {return 0}// 1. 問題分解// 1.1 求解左子樹的高度l := treeDepth(root.Left)// 1.2 求解右子樹的高度r := treeDepth(root.Right)if math.Abs(float64(l-r)) > 1 {isBalanced = false // 不是平衡樹,更改全局變量return -1          // 加一個標記-1，已經不可能是平衡樹了（減少遞歸計算次數）,直接返回}// 1.3 求解當前樹的高度dep := math.Max(float64(l), float64(r)) + 1return int(dep)
}

具體完整代碼你可以參考下面視頻的詳細講解。

• Python編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372113

• Java編碼：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1367352

• Golang編碼：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1364777

4.小結

二叉樹平衡性的判斷，可以通過二叉樹的高度來完成，即先求解二叉樹的左右子樹的高度，再判斷左右子樹高度差是否超過1，如果超過1則不是平衡二叉樹。

《數據結構與算法》深度精講課程正式上線啦！七大核心算法模塊全解析：

? ? ? 鏈表

? ? ? 二叉樹

? ? ? 二分查找、排序

? ? ? 堆、棧、隊列

? ? ? 回溯算法

? ? ? 哈希算法

? ? ? 動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建扎實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：數據結構筆試面試算法-Python語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Python語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ss897667807

• Java編碼實現：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ss161443488

• Golang編碼實現：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ss63997

對于二叉樹的相關算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：長風破浪會有時，直掛云帆濟滄海。