本題來自左神《程序員代碼面試指南》“判斷二叉樹是否為平衡二叉樹”題目。

題目

平衡二叉樹的性質為：要么是一棵空樹，要么任何一個節點的左右子樹高度差的絕對值不超過 1。

給定一棵二叉樹的頭節點 head，判斷這棵二叉樹是否為平衡二叉樹。

要求：如果二叉樹的節點數為 N，則要求時間復雜度為 O(N)。

---

題解

平衡二叉樹的標準是：對任何子樹來說，左子樹和右子樹的高度差都不超過1。本題解法的整體過程為 樹形 dp 套路，請讀者先閱讀 “找到二叉樹中的最大搜索二叉子樹” 問題了解這個套路，本題是這個套路的再次展示。

首先，樹形dp 套路的前提是滿足的。依次考查每個節點為頭節點的子樹，如果都是平衡二叉樹，那么整體就是平衡二叉樹。

樹形 dp 套路第一步

以某個節點X 為頭節點的子樹中，分析答案有哪些可能性，并且這種分析是以X 的左子樹、X 的右子樹和X 整棵樹的角度來考慮可能性的。

• 可能性一：如果 X 的左子樹不是平衡的，則以 X 為頭節點的樹就是不平衡的。
• 可能性二：如果 X 的右子樹不是平衡的，則以 X 為頭節點的樹就是不平衡的。
• 可能性三：如果 X 的左子樹和右子樹高度差超過 1，則以 X 為頭節點的樹就是不平衡的。
• 可能性四：如果上面可能性都沒中，那么以 X 為頭節點的樹是平衡的。

樹形 dp 套路第二步

根據第一步的可能性分析，列出所有需要的信息。左子樹和右子樹都需要知道各自是否平衡，以及高度這兩個信息。

樹形 dp 套路第三步

根據第二步信息匯總。定義信息如 ReturnType 類所示。

樹形 dp 套路第四步

設計遞歸函數。遞歸函數是處理以X 為頭節點的情況下的答案，包括設計遞歸的 base case，默認直接得到左樹和右樹所有的信息，以及把可能性做整合，并且也返回第三步的信息結構這四個小步驟。本題的遞歸實現請看以下的 process 方法，主函數是以下的 isBalanced 方法。

---

代碼

含測試用例

package chapter_3_binarytreeproblem;public class Problem_13_IsBalancedTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static boolean isBalanced(Node head) {return process(head).isBalanced;}public static class ReturnType {public boolean isBalanced;public int height;public ReturnType(boolean isBalanced, int height) {this.isBalanced = isBalanced;this.height = height;}}public static ReturnType process(Node head) {if (head == null) {return new ReturnType(true, 0);}ReturnType leftData = process(head.left);ReturnType rightData = process(head.right);int height = Math.max(leftData.height, rightData.height) + 1;boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;return new ReturnType(isBalanced, height);}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);System.out.println(isBalanced(head));}}

總結

以上是生活随笔為你收集整理的左神算法：判断二叉树是否为平衡二叉树（树形dp套路，Java版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。