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

（不是我們平時意義上的必須為搜索樹）

判斷一棵樹是否為平衡二叉樹：

?

可以暴力判斷：每一顆樹是否為平衡二叉樹。

?

分析：

如果左右子樹都已知是平衡二叉樹，而左子樹和右子樹高度差絕對值不超過1，本樹就是平衡的。

?

為此我們需要的信息：左右子樹是否為平衡二叉樹。左右子樹的高度。

?

我們需要給父返回的信息就是：本棵樹是否是平衡的、本棵樹的高度。

?

定義結點和返回值：

	public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}

	public static class ReturnType {public int level;   //深度public boolean isB;//本樹是否平衡public ReturnType(int l, boolean is) {level = l;isB = is;}}

我們把代碼寫出來：

	// process(head, 1)public static ReturnType process(Node head, int level) {if (head == null) {return new ReturnType(level, true);}//取信息ReturnType leftSubTreeInfo = process(head.left, level + 1);if(!leftSubTreeInfo.isB) {return new ReturnType(level, false);     //左子樹不是->返回}ReturnType rightSubTreeInfo = process(head.right, level + 1);if(!rightSubTreeInfo.isB) {return new ReturnType(level, false);     //右子樹不是->返回}if (Math.abs(rightSubTreeInfo.level - leftSubTreeInfo.level) > 1) {return new ReturnType(level, false);     //左右高度差大于1->返回}return new ReturnType(Math.max(leftSubTreeInfo.level, rightSubTreeInfo.level), true);//返回高度和true（當前樹是平衡的）}

我們不需要每次都返回高度，用一個全局變量記錄即可。

對于其它二叉樹問題，可能不止一個變量信息，所以，全局記錄最好都養成定義數組的習慣。

下面貼出完整代碼：

import java.util.LinkedList;
import java.util.Queue;public class Demo {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}public static boolean isBalance(Node head) {boolean[] res = new boolean[1];res[0] = true;getHeight(head, 1, res);return res[0];}public static class ReturnType {public int level;   //深度public boolean isB;//本樹是否平衡public ReturnType(int l, boolean is) {level = l;isB = is;}}// process(head, 1)public static ReturnType process(Node head, int level) {if (head == null) {return new ReturnType(level, true);}//取信息ReturnType leftSubTreeInfo = process(head.left, level + 1);if(!leftSubTreeInfo.isB) {return new ReturnType(level, false);     //左子樹不是->返回}ReturnType rightSubTreeInfo = process(head.right, level + 1);if(!rightSubTreeInfo.isB) {return new ReturnType(level, false);     //右子樹不是->返回}if (Math.abs(rightSubTreeInfo.level - leftSubTreeInfo.level) > 1) {return new ReturnType(level, false);     //左右高度差大于1->返回}return new ReturnType(Math.max(leftSubTreeInfo.level, rightSubTreeInfo.level), true);//返回高度和true（當前樹是平衡的}public static int getHeight(Node head, int level, boolean[] res) {if (head == null) {return level;//返回高度}//取信息//相同邏輯int lH = getHeight(head.left, level + 1, res);if (!res[0]) {return level;}int rH = getHeight(head.right, level + 1, res);if (!res[0]) {return level;}if (Math.abs(lH - rH) > 1) {res[0] = false;}return Math.max(lH, rH);//返回高度}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(isBalance(head));}}

?