0110. Balanced Binary Tree (Easy)

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]:

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
2
3
4
5
6
7

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

分析/解題

題目給定一個二元樹，試檢查其是否為高度平衡的狀態。
前面已經提到過很多次，若是一棵樹長得不夠平均(例如都長在同一邊)，那麼在進行一些操作的時候會相當耗時間，
這也是為什麼我們會在意一棵樹高度是否平衡的原因。

而題目給的條件其實以更常見的定義來說，會定義成如下所述。
假如底下3點成立，一棵非空的二元樹就被稱作是平衡的：

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

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

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

1
2
3
4
5
6

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來記錄是否已經發生不平衡的情況，
一旦發生，其實可以不用繼續往下做。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

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

Python

面試實際可能會遇到的問題

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

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