LeetCode Digest
3 分鐘 閱讀文 (大約 504 個字)

Merge Two Binary Trees

題目

做法一：recursive - DFS

  1. 找出最小的可重複動作：merge 兩個 nodes

    • 題目給的 method 就可以用來做遞迴

  2. 假設 mergeTrees 已完成，實作此最小可重複動作 

    1
    2
    3
    4
    root1.val += root2.val
    root1.left = self.mergeTrees(root1.left, root2.left)
    root1.right = self.mergeTrees(root1.right, root2.right)
    return root1

  3. 寫出遞迴的終止條件

    1
    2
    if not root1 or not root2:
        return root1 or root2

Python3 solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root1 or not root2:
        return root1 or root2
    root1.val += root2.val
    root1.left = self.mergeTrees(root1.left, root2.left)
    root1.right = self.mergeTrees(root1.right, root2.right)
    return root1

假設兩棵樹有較少節點的那顆有 n 個節點

  • 時間複雜度：O(n)
  • 空間複雜度：n 個節點那棵樹的深度
    • 最差情況是 O(n), 平均為 O(log n)

做法二：iterative - BFS

  1. 準備一個 stack 來放待 merge 的 node pairs
  2. 一次從裡面拿一個 pair 出來 merge, 同時也把該 merge 的子節點 pair 丟進去。一直做到 stack 裡面沒東西為止
  3. 因為這邊是 merge 到 root1, 故最後回傳 root1
    • 注意不要回傳到 p, 而是應該回傳當初的根節點 root1

Python3 solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root1 or not root2:
        return root1 or root2
    stack = [(root1, root2)]
    while stack:
        p, q = stack.pop()  # 使用暫時的變數 p, q 來操作節點 merge
        p.val += q.val
        if not p.left and q.left:
            p.left = q.left
        elif p.left and q.left:
            stack.append((p.left, q.left))
        if not p.right and q.right:
            p.right = q.right
        elif p.right and q.right:
            stack.append((p.right, q.right))
    return root1

假設兩棵樹有較少節點的那顆有 n 個節點

  • 時間複雜度：O(n)
    • stack 裡會有 n 個 pairs, 所以會做 n 次
  • 空間複雜度：O(n)
    • 需要大小為 n 的 stack
# , , , ,
Unique Paths
Balanced Binary 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

×