要求：判斷一顆二叉樹是否平衡。
平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有别于AVL算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
1 一般遞歸
TreeNode.java
package BinaryTree;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(TreeNode l, TreeNode r, int v) {
left = l;
right = r;
val = v;
}
public TreeNode(int v) {
val = v;
}
}
【核心】BinaryTreeTest.java
public class BinaryTreeTest {
private int getDepth(TreeNode t) {
if (t == null) {
return ;
}
int leftDepth = getDepth(t.left);
int rightDepth = getDepth(t.right);
return leftDepth > rightDepth ? leftDepth + : rightDepth + ;
}
public boolean isBalanced(TreeNode t) {
// 空樹是平衡二叉樹
if (t == null) {
return true;
}
// 判斷根節點的平衡因子是否大于1 或者 小于-1
int leftDepth = getDepth(t.left);
int rightDepth = getDepth(t.right);
int balanceFactor = leftDepth - rightDepth;
if (balanceFactor > || balanceFactor < -) {
return false;
}
// 如果跟節點的平衡因子正常，則判斷它的左右子樹是否為平衡二叉樹
else {
return isBalanced(t.left) && isBalanced(t.right);
}
}
}
測試
package BinaryTree;
public class Main {
public static void main(String[] args) {
/***
* 建立一個二叉樹：
*
* 15
* / \
* 12 25
* / \
* 9 13
* ***/
TreeNode root = new TreeNode();
TreeNode l = new TreeNode();
root.left = l;
TreeNode r = new TreeNode();
root.right = r;
TreeNode ll = new TreeNode();
TreeNode lr = new TreeNode();
l.left = ll;
l.right = lr;
BinaryTreeTest bTreeTest = new BinaryTreeTest();
Boolean ret = bTreeTest.isBalanced(root);
System.out.println(ret.toString());
//在 9 的右邊再添加一個節點 10，再判斷這顆樹是否平衡
ll.right = new TreeNode();
ret = bTreeTest.isBalanced(root);
System.out.println(ret.toString());
}
}
output：
true
false
該方法的問題在于，getDepth方法已經是在遞歸，每次判斷一個節點的深度就周遊了一遍子樹，而在判斷是否平衡的時候又要周遊一編整個樹，是以，上面的一般遞歸的算法存在多次周遊的問題，樹的結構一旦比較大就不能使用這種方法了。
2 一次周遊的遞歸算法
目标：我們希望對整個樹進行一次周遊就得到我們想要的結果。
這個目标可以實作嗎？ 我們來分析一下。首先，對于判斷一顆二叉樹是否平衡的問題的核心其實就是要獲得所有節點的深度。上面的getDepth算法就是每次都從葉子節點開始往根節點復原，進而得到根節點的深度，實際上在這個過程中，是以的節點的深度都計算了一遍，是以，我們的目标是可行的，而且方法就是從葉子節點往上周遊。
那麼，怎麼樣才能做到從葉子往上周遊呢？我們不妨想想【後序周遊】是不是就是這樣？每次都是先通路完左右子樹才通路根節點的！是以，這裡我們就是要利用這種方法，一邊周遊，一邊計算每個節點是不是平衡的。
/**
* isBalancedImproved的包裝方法
**/
public boolean isBalancedImproved(TreeNode t) {
return isBalancedImproved(t, -);
}
/**
* t: 子樹的根節點 depth: 子樹的深度。這個參數是用來向上層傳遞這一節點的計算結果的
**/
private boolean isBalancedImproved(TreeNode t, int depth) {
if (t == null) {
depth = ;
return true;
}
int leftDepth = -;
int rightDepth = -;
int balanceFactor;
// 如果 左子樹 和 右子樹 都是平衡的？
if (isBalancedImproved(t.left, leftDepth) && isBalancedImproved(t.right, rightDepth)) {
// 判斷根節點的平衡因子
balanceFactor = leftDepth - rightDepth;
if (balanceFactor > || balanceFactor < -) {
// 隻要出現不平衡的子樹就不要繼續往上判斷了
return false;
} else {
// 如果兩個子樹都為平衡的，則要繼續往上層判斷
depth = leftDepth > rightDepth ? leftDepth + : rightDepth + ;
return true;
}
} else {
return false;
}
}
将上面的測試代碼略做修改之後進行測試：
BinaryTreeTest bTreeTest = new BinaryTreeTest();
Boolean ret = bTreeTest.isBalancedImproved(root);
System.out.println(ret.toString());
//在 的右邊再添加一個節點 ，再判斷這顆樹是否平衡
ll.right = new TreeNode();
ret = bTreeTest.isBalancedImproved(root);
System.out.println(ret.toString());
結果：
true
true
這明星是錯的啊！！！！！！！！！！！！
部落客經過檢查，發現了一個常見問題，那就是java的方法參數傳遞的時候全部都是clone變量，也就是深複制，所 isBalancedImproved(TreeNode t, int depth) 方法并不難像我們想象的那樣可能通過參數 depth 将計算結果傳遞到上一層。結合代碼說就是：
…………
int leftDepth = -;
int rightDepth = -;
int balanceFactor;
// 如果 左子樹 和 右子樹 都是平衡的？
if (isBalancedImproved(t.left, leftDepth) && isBalancedImproved(t.right, rightDepth)) {
…………
在進行遞歸之後，這裡的leftDepth還是-1。
解決方案
将第二個參數改為一個引用型變量：類對象。是以我們建立一個内部輔助類AuxClass. （在複習的時候覺得我之前po出來的代碼邏輯和注釋還不夠清楚，是以我這裡重新寫了一份代碼，是以和上面的有一點點出入，但是思路一樣，懶得改了。）
package Depth;
public class Test {
public boolean isBalanced(TreeNode root) {
return isBalanced(root, new AuxClass());
}
private boolean isBalanced(TreeNode root, AuxClass aux) {
// 邊界條件: 到達樹的底部，下面已經沒有節點了
// 空的樹 是 平衡樹
if (root == null) {
// 葉子節點的高為0, 設定aux為0，傳回給上一層遞歸
aux.height = ;
return true;
}
// 判斷一顆樹是否平衡，需要知道它左右兩顆子樹的高度，然後根據高度差來判斷
// 先去判斷左子樹的情況
AuxClass leftHeight = new AuxClass(); // 用于儲存左子樹的高，并不是一個參數，是以初始化為-1
boolean leftResult = isBalanced(root.left, leftHeight);
// 再判斷右子樹的情況
AuxClass rightHeight = new AuxClass();
boolean rightResult = isBalanced(root.right, rightHeight);
// 如果子樹都不平衡，整課樹當然也就是不平衡
if (!leftResult || !rightResult) {
// 這裡的return并不代碼向上傳回就結束了，而是将這個false一層層繼續向上傳回
// 隻是已經傳回false了，後面的高度也就不再重要了。因為每次都是先判斷子樹的平衡性
return false;
} else {
// 即使左右子樹都是平衡的，還要判斷它的高度差
int balanceFactor = leftHeight.height - rightHeight.height;
if (balanceFactor > || balanceFactor < -) {
return false;
} else {
// 判斷到這裡，說明這顆樹的子樹都平衡，它自身也平衡，是以才有必要向上傳遞自己的高度，并傳回true
aux.height = balanceFactor > ? leftHeight.height + : rightHeight.height + ;
return true;
}
}
}
/**
* 内部類，輔助類
*/
class AuxClass {
public int height;
public AuxClass() {
height = -;
}
public AuxClass(int i) {
height = i;
}
}
public static void main(String[] args) {
Test test = new Test();
TreeNode root = new TreeNode();
TreeNode l = new TreeNode();
TreeNode r = new TreeNode();
root.left = l;
root.right = r;
System.out.println("isBalanced? : " + test.isBalanced(root));
TreeNode ll = new TreeNode();
l.left = ll;
TreeNode lll = new TreeNode();
ll.left = lll;
System.out.println("isBalanced? : " + test.isBalanced(root));
}
}
關于我在注釋中提到的【向上傳回】 的概念可以參考我的另外一篇講遞歸的文章：http://blog.csdn.net/cds86333774/article/details/50907444。
![采用ODC改善軟體品質：一個案例研究[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)