描述：給定一個(gè)二叉樹(shù)，判斷它是否是高度平衡的二叉樹(shù)。

本題高度平衡二叉樹(shù)定義：一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1。

示例1：

給定二叉樹(shù)[3,9,20,null,null,15,7]，返回true

3

/

9 20

/

15 7

示例2：

給定二叉樹(shù)[1,2,2,3,3,null,null,4,4]，返回false

1

/

2 2

/

3 3

/

4 4

從底至頂（提前終結(jié)法）

1、對(duì)二叉樹(shù)做深度優(yōu)先遍歷DFS，遞歸過(guò)程中：

1.1、終止條件：當(dāng)DFS越過(guò)葉子節(jié)點(diǎn)時(shí)，返回高度0；

1.2、返回值：

1.2.1、從底至頂，返回以每個(gè)節(jié)點(diǎn)root為根節(jié)點(diǎn)的子樹(shù)最大高度(左右子樹(shù)中最大的高度值加1max(left,right) + 1)；

1.2.2、當(dāng)我們發(fā)現(xiàn)有一例 左/右子樹(shù)高度差 ＞ 1 的情況時(shí)，代表此樹(shù)不是平衡樹(shù)，返回-1；

1.3、當(dāng)發(fā)現(xiàn)不是平衡樹(shù)時(shí)，后面的高度計(jì)算完全沒(méi)有意義，因此直接返回-1，避免后續(xù)過(guò)多的計(jì)算。

2、最差情況是對(duì)樹(shù)做一遍完整DFS，時(shí)間復(fù)雜度為O(N)。

public boolean isBalanced(TreeNode root) {

return depth(root) != -1;

}

private int depth(TreeNode root) {

if (root == null) return 0;

int left = depth(root.left);

if(left == -1) return -1;

int right = depth(root.right);

if(right == -1) return -1;

return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;

}

從頂至底（暴力法）

1、構(gòu)造一個(gè)獲取當(dāng)前節(jié)點(diǎn)最大深度的方法 depth() ，通過(guò)比較左右子樹(shù)最大高度差abs(self.depth(root.left) - self.depth(root.right))，來(lái)判斷以此節(jié)點(diǎn)為根節(jié)點(diǎn)下是否是二叉平衡樹(shù)；

2、從頂至底DFS，以每個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，遞歸判斷是否是平衡二叉樹(shù)：

2.1、若所有根節(jié)點(diǎn)都滿足平衡二叉樹(shù)性質(zhì)，則返回 True ；

2.2、若其中任何一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)時(shí)，不滿足平衡二叉樹(shù)性質(zhì)，則返回False。

3、本方法產(chǎn)生大量重復(fù)的節(jié)點(diǎn)訪問(wèn)和計(jì)算，最差情況下時(shí)間復(fù)雜度 O(N^2)

public boolean isBalanced(TreeNode root) {

if (root == null) return true;

return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);

}

private int depth(TreeNode root) {

if (root == null) return 0;

return Math.max(depth(root.left), depth(root.right)) + 1;

}

兩者思想上都類似，可能大家對(duì)于樹(shù)類型相關(guān)的題一直都很頭大，每次都是一看答案都會(huì)，自己動(dòng)手持續(xù)懵逼，所以更要注重平時(shí)練習(xí)和學(xué)習(xí)，痛苦一段時(shí)間，理解之后就會(huì)發(fā)現(xiàn)還蠻有意思的。

辛苦各位大佬看完，不勝感激，有興趣的可以關(guān)注公眾號(hào)，內(nèi)容持續(xù)更新發(fā)力，收獲滿滿，也可以微信私信，共同學(xué)習(xí)。

總結(jié)

以上是生活随笔為你收集整理的平衡二叉树的构造_LeetCode-平衡二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。