LeetCode Digest
4 分鐘 閱讀文 (大約 625 個字)

Balanced Binary Tree

題目

做法一

思路：

  1. 依照 height-balanced 的定義，需要符合每個node 的左右子樹高度差都不大於 1
  2. 假設有個 function height 可以回傳 node 的 height
    • 先不實作內容
  3. 使用這個 height 完成 isBalanced
  4. 實作 height 的內容

Python3 solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def isBalanced(self, root: Optional[TreeNode]) -> bool:
    def height(node):
        if not node:  # 終止條件
            return 0
        lh = height(node.left)
        rh = height(node.right)
        return max(lh, rh) + 1
        
    if not root:  # 終止條件
        return True
    lh = height(root.left)
    rh = height(root.right)
    
    # 即使左右子樹高度差不大於一，子樹本身還是有可能是不平衡的，所以要再加上後面的 `isBalanced` 判斷
    return abs(lh - rh) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

假設有 n 個 node, 樹的高度為 h

  • 時間複雜度：O(n^2)
    • isBalanced 除了呼叫自己之外的複雜度為 O(n)
      • 呼叫了 n - 1 次 height
    • 每個節點都呼叫了一次 isBalanced
  • 空間複雜度：O(h)
    • 因為遞迴的呼叫有 DFS 的特性，會從子節點一直呼叫到最下面的葉子節點，所以需要把那些 function calls 放進 stack 裡，等到葉子節點的呼叫到了再一一拿出來執行。因此 stack 的大小需等於呼叫的次數，也就是由根節點走到葉子節點需經過幾個點，即這棵樹的高度
      • 只需考慮一次遞迴呼叫所需空間，不需考慮全部遞迴呼叫 (譬如在 function 裡呼叫了自己兩次)，因為程式同時只會處理一個遞迴呼叫

做法二

思路：

  1. 有沒有辦法優化上面做法的時間複雜度呢？因為上面在算高度的時候就已經會算出每個節點的左右子樹的高度了，此時就可以順便看看是否平衡，不用等到最後再遞迴呼叫 isBalanced 增加複雜度

Python3 solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
def isBalanced(self, root: Optional[TreeNode]) -> bool:
    self.balanced = True
    def height(node):
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        if abs(lh - rh) > 1:
            self.balanced = False
        return max(lh, rh) + 1
        
    height(root)
    return self.balanced

假設有 n 個 node, 樹的高度為 h

  • 時間複雜度：O(n)
    • 每個節點都做過一次 height
  • 空間複雜度：O(h)
    • 同 做法一 的分析

類似題：Symmetric Tree 用 recursive 方法來解

# , , ,
Merge Two Binary Trees
Same Tree

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×