問題：
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
大意：
給出一個(gè)二叉樹，判斷它高度是不是平衡的。
對(duì)于這個(gè)問題，一個(gè)高度平衡的二叉樹是指每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的深度的差異都不超過1的二叉樹。
思路：
這道題題目說的太簡(jiǎn)略了也沒有例子，根據(jù)不斷試錯(cuò)摸出來的情況，就是說每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的深度不能想查大于1，比如左子節(jié)點(diǎn)下還有子節(jié)點(diǎn)，右子節(jié)點(diǎn)下沒有了，這是允許的，深度相差1，但是如果左子節(jié)點(diǎn)的子節(jié)點(diǎn)還有子節(jié)點(diǎn)，深度相差就是2了，就不平衡了。
如果直接判斷有無子節(jié)點(diǎn)，情況太多了不好做。不如直接遞歸記錄每個(gè)節(jié)點(diǎn)的深度，然后比較每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的深度相差是否大于1。
這里要記錄每個(gè)子節(jié)點(diǎn)的深度可以用遞歸的方法，葉子節(jié)點(diǎn)的深度為1，往上遞增，注意在遞歸算一個(gè)節(jié)點(diǎn)深度時(shí)，要判斷左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的深度哪個(gè)更深，取更深的那一個(gè)，也就是數(shù)值更大的那一個(gè)。
然后可以再判斷每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的深度相差是否大于1。但是要重新遍歷一遍所有節(jié)點(diǎn)，這無疑增加了時(shí)間。在上面我們計(jì)算每個(gè)節(jié)點(diǎn)的深度的時(shí)候，有一步是判斷左右子節(jié)點(diǎn)哪個(gè)節(jié)點(diǎn)更深，這里明顯可以直接比較相差是否大于1，如果大于1，我們將該節(jié)點(diǎn)的深度特殊記為-1這個(gè)不會(huì)出現(xiàn)的深度值，我們希望可以傳遞到最頂層去告訴題目這個(gè)二叉樹是不平衡的，因此在計(jì)算每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的時(shí)候，需要判斷左右子節(jié)點(diǎn)的深度有沒有等于-1的，如果有，說明下面有個(gè)地方出現(xiàn)不平衡了，這時(shí)候直接把-1這個(gè)信號(hào)往上傳就好了。這樣一層層遞歸傳回root，就可以根據(jù)根節(jié)點(diǎn)的深度是否是-1來判斷是否平衡了。
代碼（Java）：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
if (height(root) == -1) return false;
else return true;
}
public int height(TreeNode root) {
if (root == null) return 0;
else {
int leftHeight = height(root.left);
if (leftHeight == -1) return -1;
int rightHeight = height(root.right);
if (rightHeight == -1) return -1;
if (leftHeight - rightHeight > 1 || leftHeight - rightHeight < -1) return -1;
return Math.max(height(root.left), height(root.right)) + 1;
}
}
}
合集：https://github.com/Cloudox/LeetCode-Record
