目標：
這題主要目的在於了解平衡樹的觀念，
並幫助讀者學習如何考慮一棵樹在高度平衡時的操作所需的時間複雜度。

原題：

Question:
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.

Example 1:
Given the following tree [3,9,20,null,null,15,7]:
    3
   / \
  9  20
    /  \
   15   7
Return true.

Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
Return false.

分析/解題：
題目給定一個二元樹，試檢查其是否為高度平衡的狀態。
前面已經提到過很多次，若是一棵樹長得不夠平均(例如都長在同一邊)，
那麼在進行一些操作的時候會相當耗時間，
這也是為什麼我們會在意一棵樹高度是否平衡的原因。
而題目給的條件其實以更常見的定義來說，會定義成如下所述。
假如底下3點成立，一棵非空的二元樹就被稱作是平衡的：

1. 二元樹的左子樹是平衡的
2. 二元樹的右子樹是平衡的
3. 二元樹的左右子樹高的差不大於1
   對於一個樹的高度(或稱作深度)，
   是指從樹的根節點走到葉節點的最大長度，所以基於這點，
   我們的流程應該是從根節點往下，
   檢查以每個節點為基準的左右子樹高的差均不大於1，
   該二元樹即為平衡的，反之則為不平衡。

依此，我們會需要知道除了根以外，每個節點的深度，
故可以簡單利用遞迴來操作：

先試寫看看maxdp這個函式的虛擬碼(假設你要求root這個node的深度)：

maxdp(root) {
    if root == NIL return 0
    l = maxdp(root.left)
    r = maxdp(root.right)
    return max(l, r) + 1
}

當我們要求某個節點的深度時，
就相當於求其左右兩邊子樹深度的較大值+1。
(+1是因為經過了自己這個節點)

回到我們原本的問題，我們想要求左右子樹的深度差不能大於1的話，
只需要在maxdp函式中增加去判斷左右深度差即可。
我們同時可以使用一個變數res來記錄是否已經發生不平衡的情況，
一旦發生，其實可以不用繼續往下做。

let res = true
maxdp(root) {
    if (root == NIL or !res) return 0
    l = maxdp(root.left)
    r = maxdp(root.right)
    if (abs(l-r) > 1) {
        res = false
        return 0
    }    
    return max(l, r) + 1
}

在一開始的解答的isBalanced函式中呼叫maxdp，
最後將res回傳即可得到答案。

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public boolean res = true;
	public boolean isBalanced(TreeNode root) {
		maxdp(root);
		return res;
	}
	public int maxdp(TreeNode root) {
		if (root == null || !res) return 0;
		int l = maxdp(root.left);
		int r = maxdp(root.right);
		if (Math.abs(l-r) > 1) {
			res = false;
			return 0;
		}
		return Math.max(l, r) + 1;
	}	
}

Python這邊展示了一個再進一步的思路：
如果我們已經發現不平衡的狀況，可以使用-1做為代表，
因為深度只可能大於或等於0，那麼，只要每次檢查是否出現-1，
就不用使用額外的res變數來儲存結果，
我們只需要檢查回傳是否為-1就可以判定二元樹是不是平衡了！

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check(root):
            if root is None:
                return 0
            left  = check(root.left)
            right = check(root.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)
            
        return check(root) != -1

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(最差狀況是樹很平衡，每一層都要檢查，時間複雜度是O(N)
自行宣告的額外空間是O(1)，但遞迴中需有Call Stack，
最糟的狀況也是O(N)(全擠在同一邊))

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0062. Unique Paths (Medium)