BFS vs DFS

二元樹走訪或稱二元樹遍歷，簡單來說就是走訪樹中各節點，轉化為線性關係。

主要分成兩種策略方式

  • 深度優先搜尋（Depth-first Search，DFS）:從根節點出發，選擇某一子樹並以垂直方向由上到下處理，將其子節點訪問完後，再選擇另一子樹走訪。
  • 廣度優先搜尋（Breadth-first Search，BFS）:從根節點出發，以水平方向由左到右走訪，將同階層的兄弟節點訪問完之後，再走訪下一階層的節點。

深度優先搜尋 DFS


假設根結點為N、左子樹為L、右子樹為R

  • 前序走訪(Pre-order Traversal): NLR, 根節點 → 左子樹 → 右子樹
  • 中序走訪(In-order Traversal): LNR, 左子樹 → 根節點 → 右子樹
  • 後序走訪(Post-order Traversal): LRN, 左子樹 → 右子樹 → 根節點

簡單來說

  • 都是先左子樹，再右子樹
  • preorder: root 在前面
  • inorder: root 在中間（裡面）
  • postorder: root 在後面

preorder的實作

前序走訪： 順序是根節點、左子節點、右子節點。

Order: [1, 2, 4, 8, 9, 5, 3, 6, 10, 11, 7]

recursive: 先處理根節點 -> 假設左右子樹已經處理好 ：（再印左）->（後印右）
iterative: 使用 stack 把要先處理的節點晚點放入，先處理左子樹，再處理右子樹。那就先塞右子樹，再塞左子樹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def preorder_traversal(root):
    """
    前序遍历 (NLR)
    根节点 → 左子树 → 右子树
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # 訪問root
        dfs(node.left)           # 遞迴訪問左子樹
        dfs(node.right)          # 遞迴訪問右子樹
    
    dfs(root) # 起點：開始遞迴
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def preorder_traversal_iterative(root):
    """
    前序遍历 (NLR)
    根节点 → 左子树 → 右子树
    """
    if not root:
        return []
    
    stack, result = [root], []  # stack用來存放要處理的節點 result 是解答
    
    while stack:
        node = stack.pop()  # 起點：從root開始
        if node:
            result.append(node.val)  # root 先處理
            stack.append(node.right) # stack 後進先出：right後處理，先押入stack
            stack.append(node.left)  # stack 後進先出：left先處理，後押入stack
    
    return result

inorder的實作

中序走訪： 順序是左子節點、根節點、右子節點。

Order: [8, 4, 9, 2, 5, 1, 10, 6, 11, 3, 7]

recursive: 假設左右子樹已經處理好 ：先印左子樹 -> 印root ->後印右子樹
iterative:

  • 使用 stack 深入進去左子樹的底端
  • stack pop 出來處理(最底層的左子樹)
  • 轉向右子樹
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inorder_traversal(root):
    """
    中序遍历 (LNR)
    左子树 → 根节点 → 右子树
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # 先處理左子樹
        result.append(node.val)  # 再處理root
        dfs(node.right)          # 後處理右子樹
    
    dfs(root)   # 起點：開始遞迴
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def inorder_traversal_iterative(root):
    """
    中序遍历 (LNR)
    左子树 → 根节点 → 右子树
    """
    stack, result = [], []
    current = root
    
    while stack or current:
        # 要先把整個左邊處理完，因此要先一直塞left到底
        while current:
            stack.append(current)
            current = current.left  # 一直向左子樹走
        
        # 把stack中所有的左子樹節點進行處理
        current = stack.pop()
        result.append(current.val)  # 處理 left -> root 
        current = current.right     # 最後，轉向當前左子樹最底的右節點
    
    return result

postorder的實作

後序走訪： 順序是左子節點、右子節點、根節點。

Order: [8, 9, 4, 5, 2, 10, 11, 6, 7, 3, 1]

recursive: 假設左右子樹已經處理好 ：先印左子樹 -> 後印右子樹 -> 印root
iterative:

  • 很像preorder前序走訪，只是 順序是根節點、右子節點、左子節點。
  • 因此我們可以使用preorder的方式，但是要先append右子樹，再append左子樹
  • 最後再reverse整個結果列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def postorder_traversal(root):
    """
    后序遍历 (LRN)
    左子树 → 右子树 → 根节点
    """
    result = []
    
    def dfs(node):
        if not node:
            return
        dfs(node.left)           # 遞迴訪問左子樹
        dfs(node.right)          # 遞迴訪問右子樹
        result.append(node.val)  # 訪問root
    
    dfs(root)
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def postorder_traversal_iterative(root):
    """
    后序遍历 (LRN)
    左子树 → 右子树 → 根节点
    """
    if not root:
        return []
    
    stack, result = [root], []
    while stack:
        node = stack.pop()
        if node:
            result.append(node.val)  # 訪問root
            stack.append(node.left)  # 因為最後會reverse，所以先處理右子樹，因此先押入左子樹
            stack.append(node.right) # 因為最後會reverse，所以後處理左子樹，因此後押入右子樹
    
    result.reverse()  # 最後反轉結果列表
    return result

Morris Traversal

很多時候題目會要求 O(1) 空間複雜度，這時候我們可以使用 Morris Traversal 來達成，但是此方法直接修改原始樹，但可以保證空間複雜度為 O(1)，因此使用的時候要注意是否可以改動到原始樹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    1
   / \
  2   5
 / \   \
3   4   6

// 將 1 的 left sub-tree 插入 right sub-tree 的地方
    1
     \
      2         5
     / \         \
    3   4         6        

// 將原本的right sub-tree 接到 left sub-tree 的最右邊節點
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6

 // 將 2 的 left sub-tree 插入 right sub-tree 的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   

 // 將原本的 right sub-tree 接到 left sub-tree 的最右邊節點
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         

......

程式碼 preorder-morris-traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def flatten2(self, root: Optional[TreeNode]) -> TreeNode:
    cur = root
    while cur:
        if cur.left:
            # 1. 先找到左樹最右邊的node rightmost
            rightmost = cur.left
            while rightmost.right:
                rightmost = rightmost.right

            # 2. 把 cur 的右樹接到 rightmost.right, 然後再把 cur.right 接到 left
            rightmost.right = cur.right
            cur.right = cur.left
            cur.left = None

        # 3. cur 換成 cur.right
        cur = cur.right

廣度優先搜尋 BFS

層序走訪： 順序是由根節點一層一層往下，由左往右。

Order: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

recursive: next_level 是拿來存放下一層的節點，values 當前層的解答，最後把 values 加入 result 中。
iterative: 跟recursive不會有太大的差異，反而比較好理解，就是把下一層要處理的節點放入 queue （先進先出） 中，然後處理當前節點，只要發現當前的節點仍有下一層，那就放到queue等等處理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def bfs_recursive(root):
    """
    广度优先搜索 (递归实现)
    """
    def bfs_level(nodes):
        if not nodes:
            return
        next_level, values = [], []
        for node in nodes:
            values.append(node.val)
            if node.left:
                next_level.append(node.left) 
            if node.right:
                next_level.append(node.right)  
        result.append(values)
        bfs_level(next_level)

    result = []
    if root:
        bfs_level([root])
    return [val for sublist in result for val in sublist] # flatten result 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def bfs_iterative(root):
    """
    广度优先搜索 (迭代实现)
    """
    if not root:
        return []

    queue = deque([root])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

總結

DFS複雜：使用Stack先進後出
使用recursive會比較容易

  • 大問題：要走訪整個樹
  • 小問題：
    • 假設左右子樹已經走訪 recursive 左右子樹，最後結合root即可

使用iterative會比較複雜

  • preorder 因為需要先完整的走到底 (左子樹)，因此可以先印root，然後先放 right 再放 left，這樣 pop 就會處理 按後進先出原則，先處理left再處理right。
  • postorder 比較特別，記住他是 preorder (但是先處理右子樹，再處理左子樹)的相反，因此可以使用跟 preorder 一樣的方式，只是stack先放left再放right，最後再reverse整個結果列表。
  • inorder 比較特殊，因為 root 放在中間，這意味著要先把左子樹走完，為了先走到底，我們要用 while loop 一直往左子樹底部走直到觸底，然後再處理root，最後轉向右子樹。

BFS單純：使用Queue先進先出
使用 recursive 或是 iterative 所需要的概念都相同

  • 那就是都是先把下一層要處理的節點放入 queue 中，然後處理當前節點，只要發現當前的節點仍有下一層，那就放到queue等等處理。

Ref