多叉树遍历算法详解

本文最后更新于：1 天前

多叉树遍历算法详解

Java 实现 - 递归遍历（三种）+ 层序遍历（三种）

📖 目录

🌲 树结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 多叉树节点类
class TreeNode {
    int val;                    // 节点值
    List<TreeNode> children;   // 子节点列表
    
    TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
    
    TreeNode(int val, List<TreeNode> children) {
        this.val = val;
        this.children = children;
    }
}

测试树结构

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

🔄 递归遍历

1️⃣ 前序遍历 (Preorder Traversal)

遍历顺序：根节点 → 所有子节点（从左到右）

1
输出：1 2 5 8 6 3 4 7

算法思路：

  1. 访问根节点
  2. 递归遍历所有子节点（从左到右）

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> preorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorderHelper(root, result);
    return result;
}

private void preorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    
    // 1. 访问根节点
    result.add(node.val);
    
    // 2. 递归遍历所有子节点
    for (TreeNode child : node.children) {
        preorderHelper(child, result);
    }
}

2️⃣ 后序遍历 (Postorder Traversal)

遍历顺序：所有子节点（从左到右）→ 根节点

1
输出：8 5 6 2 3 7 4 1

算法思路：

  1. 递归遍历所有子节点（从左到右）
  2. 访问根节点

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorderHelper(root, result);
    return result;
}

private void postorderHelper(TreeNode node, List<Integer> result) {
    if (node == null) return;
    
    // 1. 递归遍历所有子节点
    for (TreeNode child : node.children) {
        postorderHelper(child, result);
    }
    
    // 2. 访问根节点
    result.add(node.val);
}

3️⃣ 深度优先遍历 (DFS)

遍历顺序：与前序遍历类似，使用栈实现非递归版本

1
输出：1 2 5 8 6 3 4 7

算法思路：

  1. 使用栈模拟递归
  2. 弹出一个节点，访问它
  3. 将其子节点反向入栈（保持从左到右顺序）

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> dfs(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        // 反向入栈，保持从左到右的访问顺序
        List<TreeNode> children = node.children;
        for (int i = children.size() - 1; i >= 0; i--) {
            stack.push(children.get(i));
        }
    }
    
    return result;
}

📊 层序遍历

1️⃣ 标准层序遍历

遍历顺序：按层次顺序访问所有节点

1
输出：1 2 3 4 5 6 7 8

算法思路：

  1. 使用队列进行广度优先搜索
  2. 按层次依次访问节点

Java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Integer> levelOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.val);
        
        // 将所有子节点加入队列
        for (TreeNode child : node.children) {
            queue.offer(child);
        }
    }
    
    return result;
}

2️⃣ 按层遍历

遍历顺序：每层的节点作为单独的列表返回

1
输出：[[1], [2, 3, 4], [5, 6, 7], [8]]

算法思路：

  1. 使用队列进行层次遍历
  2. 记录每层的节点数量
  3. 一次性处理一层的所有节点

Java 实现：

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
public List<List<Integer>> levelOrderByLevel(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 levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        // 处理当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            // 将当前层的所有子节点加入队列
            for (TreeNode child : node.children) {
                queue.offer(child);
            }
        }
        
        result.add(level);
    }
    
    return result;
}

3️⃣ 之字形层序遍历 (Zigzag)

遍历顺序：奇数层从左到右，偶数层从右到左

1
输出：[[1], [4, 3, 2], [5, 6, 7], [8]]

算法思路：

  1. 使用队列进行层次遍历
  2. 使用布尔变量控制是否反转
  3. 偶数层反转列表顺序

Java 实现：

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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean reverse = false;  // 控制是否反转
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            for (TreeNode child : node.children) {
                queue.offer(child);
            }
        }
        
        // 偶数层反转顺序
        if (reverse) {
            Collections.reverse(level);
        }
        result.add(level);
        
        reverse = !reverse;
    }
    
    return result;
}

💻 完整代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
import java.util.*;

/**
 * 多叉树遍历实现
 * 
 * 递归遍历（三种）：
 * 1. 前序遍历 - 根 -> 子树
 * 2. 后序遍历 - 子树 -> 根
 * 3. 深度优先遍历 - 非递归DFS
 * 
 * 层序遍历（三种）：
 * 1. 标准层序遍历 - 逐层访问
 * 2. 按层遍历 - 每层单独输出
 * 3. 之字形层序遍历 - 锯齿形遍历
 */
public class NTreeTraversal {

    // ==================== 多叉树节点类 ====================
    
    static class TreeNode {
        int val;
        List<TreeNode> children;
        
        TreeNode(int val) {
            this.val = val;
            this.children = new ArrayList<>();
        }
        
        TreeNode(int val, List<TreeNode> children) {
            this.val = val;
            this.children = children;
        }
    }
    
    // ==================== 递归遍历 ====================
    
    /**
     * 前序遍历 (Preorder Traversal)
     * 顺序：根节点 -> 所有子节点（从左到右）
     */
    public List<Integer> preorder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }
    
    private void preorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 先访问根节点
        result.add(node.val);
        // 再递归访问所有子节点
        for (TreeNode child : node.children) {
            preorderHelper(child, result);
        }
    }
    
    /**
     * 后序遍历 (Postorder Traversal)
     * 顺序：所有子节点（从左到右）-> 根节点
     */
    public List<Integer> postorder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }
    
    private void postorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 先递归访问所有子节点
        for (TreeNode child : node.children) {
            postorderHelper(child, result);
        }
        // 最后访问根节点
        result.add(node.val);
    }
    
    /**
     * 深度优先遍历 (DFS) - 非递归实现
     */
    public List<Integer> dfs(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            
            // 反向入栈，保持从左到右的访问顺序
            List<TreeNode> children = node.children;
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }
        
        return result;
    }
    
    // ==================== 层序遍历 ====================
    
    /**
     * 标准层序遍历 (Level Order Traversal)
     * 按层次顺序访问所有节点
     */
    public List<Integer> levelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            
            // 将所有子节点加入队列
            for (TreeNode child : node.children) {
                queue.offer(child);
            }
        }
        
        return result;
    }
    
    /**
     * 按层遍历 (Level by Level)
     * 每层的节点作为单独的列表返回
     */
    public List<List<Integer>> levelOrderByLevel(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 levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            // 处理当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                // 将当前层的所有子节点加入队列
                for (TreeNode child : node.children) {
                    queue.offer(child);
                }
            }
            
            result.add(level);
        }
        
        return result;
    }
    
    /**
     * 之字形层序遍历 (Zigzag Level Order)
     * 奇数层从左到右，偶数层从右到左
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean reverse = false;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                for (TreeNode child : node.children) {
                    queue.offer(child);
                }
            }
            
            // 偶数层反转顺序
            if (reverse) {
                Collections.reverse(level);
            }
            result.add(level);
            
            reverse = !reverse;
        }
        
        return result;
    }
    
    // ==================== 测试代码 ====================
    
    public static void main(String[] args) {
        NTreeTraversal traversal = new NTreeTraversal();
        
        // 构建测试多叉树
        //       1
        //    /  |  \
        //   2   3  4
        //  / \     \
        // 5   6     7
        //  |
        // 8
        
        TreeNode node8 = new TreeNode(8);
        TreeNode node5 = new TreeNode(5, Arrays.asList(node8));
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2, Arrays.asList(node5, node6));
        
        TreeNode node3 = new TreeNode(3);
        TreeNode node7 = new TreeNode(7);
        TreeNode node4 = new TreeNode(4, Arrays.asList(node7));
        
        TreeNode root = new TreeNode(1, Arrays.asList(node2, node3, node4));
        
        System.out.println("========== 递归遍历 ==========");
        
        System.out.print("前序遍历: ");
        System.out.println(traversal.preorder(root));
        
        System.out.print("后序遍历: ");
        System.out.println(traversal.postorder(root));
        
        System.out.print("DFS遍历: ");
        System.out.println(traversal.dfs(root));
        
        System.out.println("\n========== 层序遍历 ==========");
        
        System.out.print("标准层序: ");
        System.out.println(traversal.levelOrder(root));
        
        System.out.print("按层遍历: ");
        System.out.println(traversal.levelOrderByLevel(root));
        
        System.out.print("之字形遍历: ");
        System.out.println(traversal.zigzagLevelOrder(root));
    }
}

🧪 测试结果

1
2
3
4
5
6
7
8
9
========== 递归遍历 ==========
前序遍历: [1, 2, 5, 8, 6, 3, 4, 7]
后序遍历: [8, 5, 6, 2, 3, 7, 4, 1]
DFS遍历: [1, 2, 5, 8, 6, 3, 4, 7]

========== 层序遍历 ==========
标准层序: [1, 2, 3, 4, 5, 6, 7, 8]
按层遍历: [[1], [2, 3, 4], [5, 6, 7], [8]]
之字形遍历: [[1], [4, 3, 2], [5, 6, 7], [8]]

📊 复杂度分析

算法 时间复杂度 空间复杂度
前序遍历 O(n) O(h)
后序遍历 O(n) O(h)
DFS O(n) O(h)
标准层序 O(n) O(w)
按层遍历 O(n) O(w)
之字形遍历 O(n) O(w)

说明：

  • n：节点总数
  • h：树的高度
  • w：树的最大宽度（某一层最多的节点数）

📝 总结

遍历类型 方法 核心数据结构 特点
递归遍历 前序 递归栈 根→子
递归遍历 后序 递归栈 子→根
递归遍历 DFS 显式栈 非递归实现
层序遍历 标准 队列 逐层访问
层序遍历 按层 队列 返回分层结果
层序遍历 之字形 队列 交替反转

本文档详细介绍了多叉树的六种遍历算法，包括递归和迭代两种实现方式。

算法学习
#算法 #数据结构
多叉树遍历算法详解
https://alleyf.github.io/2026/03/d4bf9735580a.html
作者
alleyf
发布于
2026年3月9日
更新于
2026年3月9日
许可协议