問(wèn)題：
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è)二叉樹(shù)调炬，判斷它高度是不是平衡的逾滥。
對(duì)于這個(gè)問(wèn)題菱涤，一個(gè)高度平衡的二叉樹(shù)是指每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的深度的差異都不超過(guò)1的二叉樹(shù)。
思路：
這道題題目說(shuō)的太簡(jiǎn)略了也沒(méi)有例子佑女，根據(jù)不斷試錯(cuò)摸出來(lái)的情況，就是說(shuō)每個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的深度不能想查大于1，比如左子節(jié)點(diǎn)下還有子節(jié)點(diǎn)趴乡，右子節(jié)點(diǎn)下沒(méi)有了，這是允許的蝗拿，深度相差1晾捏，但是如果左子節(jié)點(diǎn)的子節(jié)點(diǎn)還有子節(jié)點(diǎn)，深度相差就是2了哀托，就不平衡了惦辛。
如果直接判斷有無(wú)子節(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)，這無(wú)疑增加了時(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è)二叉樹(shù)是不平衡的绕沈，因此在計(jì)算每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的時(shí)候锐想，需要判斷左右子節(jié)點(diǎn)的深度有沒(méi)有等于-1的，如果有七冲，說(shuō)明下面有個(gè)地方出現(xiàn)不平衡了痛倚，這時(shí)候直接把-1這個(gè)信號(hào)往上傳就好了。這樣一層層遞歸傳回root澜躺，就可以根據(jù)根節(jié)點(diǎn)的深度是否是-1來(lái)判斷是否平衡了蝉稳。
代碼（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
