二元樹遍歷（Binary Tree Traversal）完整指南

by Bill.Lin 6 分鐘閱讀
Algorithm

概述

二元樹遍歷是資料結構與演算法中的基本概念，主要有三種遍歷方式：前序遍歷（PreOrder）、中序遍歷（InOrder）、後序遍歷（PostOrder）。每種遍歷方式都有其特定的應用場景和優勢。

基本概念

考慮以下二元樹結構：

1
2
3
4
5

        4
       / \
      2   6
     / \ / \
    1  3 5  7

三種遍歷方式的順序

  1. 前序遍歷（PreOrder）：中 → 左 → 右

    • 遍歷順序：4 → 2 → 1 → 3 → 6 → 5 → 7

  2. 中序遍歷（InOrder）：左 → 中 → 右

    • 遍歷順序：1 → 2 → 3 → 4 → 5 → 6 → 7
    • 對於二元搜尋樹，中序遍歷可得到有序序列

  3. 後序遍歷（PostOrder）：左 → 右 → 中

    • 遍歷順序：1 → 3 → 2 → 5 → 7 → 6 → 4

遍歷實作

1. 中序遍歷（InOrder Traversal）

中序遍歷在二元搜尋樹中特別有用，因為它會按升序訪問所有節點。

遞歸實作

1
2
3
4
5
6
7

public void inorderTraversal(TreeNode root) {
    if (root == null) return;
    
    inorderTraversal(root.left);   // 遍歷左子樹
    System.out.print(root.val + " "); // 處理根節點
    inorderTraversal(root.right);  // 遍歷右子樹
}

迭代實作（使用堆疊）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 將所有左子節點推入堆疊
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 處理堆疊頂部節點
        current = stack.pop();
        result.add(current.val);
        
        // 移動到右子樹
        current = current.right;
    }
    
    return result;
}

2. 前序遍歷（PreOrder Traversal）

前序遍歷適用於複製樹結構或建立表達式樹等場景。

遞歸實作

1
2
3
4
5
6
7

public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    
    System.out.print(root.val + " "); // 處理根節點
    preorderTraversal(root.left);   // 遍歷左子樹
    preorderTraversal(root.right);  // 遍歷右子樹
}

迭代實作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        result.add(current.val);
        
        // 注意：先推入右子節點，再推入左子節點
        // 這樣確保左子節點先被處理
        if (current.right != null) {
            stack.push(current.right);
        }
        if (current.left != null) {
            stack.push(current.left);
        }
    }
    
    return result;
}

3. 後序遍歷（PostOrder Traversal）

後序遍歷適用於計算樹的大小、刪除節點或計算表達式值等場景。

遞歸實作

1
2
3
4
5
6
7

public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    
    postorderTraversal(root.left);  // 遍歷左子樹
    postorderTraversal(root.right); // 遍歷右子樹
    System.out.print(root.val + " "); // 處理根節點
}

迭代實作

 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

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisited = null;
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            TreeNode peekNode = stack.peek();
            // 如果右子節點存在且未被訪問過
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                result.add(peekNode.val);
                lastVisited = stack.pop();
            }
        }
    }
    
    return result;
}

實際應用：從遍歷序列重建二元樹

1. 從中序與後序遍歷重建二元樹

LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

 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

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || 
            postorder == null || postorder.length == 0) {
            return null;
        }
        return helper(postorder, postorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode helper(int[] postorder, int postIndex, 
                           int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd || postIndex < 0) {
            return null;
        }
        
        // 後序遍歷的最後一個元素是根節點
        TreeNode root = new TreeNode(postorder[postIndex]);
        
        // 在中序遍歷中找到根節點的位置
        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                rootIndex = i;
                break;
            }
        }
        
        // 遞歸建構左右子樹
        // 注意：先建構右子樹，因為後序遍歷是左-右-根
        root.right = helper(postorder, postIndex - 1, 
                           inorder, rootIndex + 1, inEnd);
        root.left = helper(postorder, postIndex - (inEnd - rootIndex + 1), 
                          inorder, inStart, rootIndex - 1);
        
        return root;
    }
}

2. 從前序與中序遍歷重建二元樹

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

 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

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, inorder, 0, 0, inorder.length - 1);
    }
    
    private TreeNode helper(int[] preorder, int[] inorder, 
                           int preStart, int inStart, int inEnd) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        
        // 前序遍歷的第一個元素是根節點
        TreeNode root = new TreeNode(preorder[preStart]);
        
        // 在中序遍歷中找到根節點的位置
        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == preorder[preStart]) {
                rootIndex = i;
                break;
            }
        }
        
        // 遞歸建構左右子樹
        root.left = helper(preorder, inorder, preStart + 1, 
                          inStart, rootIndex - 1);
        root.right = helper(preorder, inorder, preStart + rootIndex - inStart + 1, 
                           rootIndex + 1, inEnd);
        
        return root;
    }
}

時間與空間複雜度

遍歷方式時間複雜度空間複雜度（遞歸）空間複雜度（迭代）
前序遍歷O(n)O(h)O(h)
中序遍歷O(n)O(h)O(h)
後序遍歷O(n)O(h)O(h)

其中 n 是節點數量，h 是樹的高度（最壞情況下 h = n，最佳情況下 h = log n）。

應用場景總結

  1. 前序遍歷：複製樹、序列化樹結構、建立表達式樹
  2. 中序遍歷：二元搜尋樹的有序輸出、驗證二元搜尋樹
  3. 後序遍歷：計算樹的大小、刪除樹、計算表達式值、釋放記憶體

層序遍歷（BFS）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Morris 遍歷（O(1) 空間）

Morris 遍歷利用葉節點的空 right 指標儲存 predecessor，實現不用 stack 的中序遍歷：

 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

public List<Integer> inorderMorris(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;

    while (curr != null) {
        if (curr.left == null) {
            result.add(curr.val);
            curr = curr.right;
        } else {
            TreeNode pred = curr.left;
            while (pred.right != null && pred.right != curr) {
                pred = pred.right;
            }
            if (pred.right == null) {
                pred.right = curr;   // 建立 thread
                curr = curr.left;
            } else {
                pred.right = null;   // 恢復樹結構
                result.add(curr.val);
                curr = curr.right;
            }
        }
    }
    return result;
}

時間 O(n)，空間 O(1)（修改指標後恢復原始結構）。

遍歷方法比較

方法時間空間適用場景
遞迴O(n)O(h) call stack程式碼簡潔，h = 樹高
迭代 + StackO(n)O(h)避免 stack overflow（深樹）
MorrisO(n)O(1)空間嚴格限制
BFSO(n)O(w)層序、最短路（w = 最寬層）

參考資料

留言討論