概述
二元樹遍歷是資料結構與演算法中的基本概念，主要有三種遍歷方式：前序遍歷（PreOrder）、中序遍歷（InOrder）、後序遍歷（PostOrder）。每種遍歷方式都有其特定的應用場景和優勢。
基本概念
考慮以下二元樹結構：
1
2
3
4
5
| 4
/ \
2 6
/ \ / \
1 3 5 7
|
三種遍歷方式的順序
前序遍歷（PreOrder）：中 → 左 → 右
- 遍歷順序：4 → 2 → 1 → 3 → 6 → 5 → 7
中序遍歷（InOrder）：左 → 中 → 右
- 遍歷順序：1 → 2 → 3 → 4 → 5 → 6 → 7
- 對於二元搜尋樹，中序遍歷可得到有序序列
後序遍歷（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）。
應用場景總結
- 前序遍歷：複製樹、序列化樹結構、建立表達式樹
- 中序遍歷：二元搜尋樹的有序輸出、驗證二元搜尋樹
- 後序遍歷：計算樹的大小、刪除樹、計算表達式值、釋放記憶體
參考資料