本题来自左神《程序员代码面试指南》“判断二叉树是否为平衡二叉树”题目。

题目

平衡二叉树的性质为：要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过 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));

	}

}