知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 二叉树的遍历 ## 题目 实现二叉树的前序、中序、后序和层序遍历。 ## 大白话理解 遍历就是"按某种顺序把树上每个节点都访问一遍"。区别在于你什么时候"处理"当前节点: ``` 前序(Pre-order):先处理自己,再去左边,再去右边 → 根 左 右 中序(In-order): 先去左边,处理自己,再去右边 → 左 根 右 后序(Post-order):先去左边,再去右边,最后处理自己 → 左 右 根 层序(Level-order):一层一层从上到下、从左到右 ``` 用吃饭来比喻: - 前序:先吃菜,再喝汤,再吃饭(先干正事) - 中序:先喝汤,再吃菜,再吃饭(正事放中间) - 后序:先喝汤,再吃饭,最后吃菜(正事放最后) ``` 1 / \ 2 3 / \ 4 5 前序:1 2 4 5 3 中序:4 2 5 1 3 后序:4 5 2 3 1 层序:1 2 3 4 5 ``` ## 递归实现(最直观) 递归的本质:把大问题拆成小问题,每个节点做同样的事。 ```java // 前序遍历 void preorder(TreeNode root, List<Integer> result) { if (root == null) return; result.add(root.val); // 先处理自己 preorder(root.left, result); // 再去左边 preorder(root.right, result); // 再去右边 } // 中序遍历 void inorder(TreeNode root, List<Integer> result) { if (root == null) return; inorder(root.left, result); // 先去左边 result.add(root.val); // 处理自己 inorder(root.right, result); // 再去右边 } // 后序遍历 void postorder(TreeNode root, List<Integer> result) { if (root == null) return; postorder(root.left, result); // 先去左边 postorder(root.right, result); // 再去右边 result.add(root.val); // 最后处理自己 } ``` 看到没?三种遍历的代码几乎一样,只是 `result.add(root.val)` 的位置不同。 ## 迭代实现(用栈模拟递归) 递归本质上是系统帮你维护了一个调用栈,迭代就是自己手动维护这个栈。 ### 前序遍历(迭代) ```java public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // 处理当前节点 // 先压右再压左(因为栈是后进先出,要让左边先出来) if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return result; } ``` ### 中序遍历(迭代) ```java public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 一路向左,把左边的节点全部压栈 while (cur != null) { stack.push(cur); cur = cur.left; } // 弹出栈顶(最左边的节点) cur = stack.pop(); result.add(cur.val); // 处理 cur = cur.right; // 转向右子树 } return result; } ``` 大白话:一直往左走到底,走不动了就回头处理,然后看看右边。 ### 后序遍历(迭代) ```java // 技巧:前序是 根→左→右,把它改成 根→右→左,然后反转结果就是 左→右→根(后序) public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> result = new LinkedList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.addFirst(node.val); // 头插法(相当于反转) if (node.left != null) stack.push(node.left); // 先压左 if (node.right != null) stack.push(node.right); // 再压右 } return result; } ``` ## 层序遍历(BFS) ```java 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; } ``` 关键技巧:每次循环开始时记录队列大小 `size`,这个 `size` 就是当前层的节点数。循环 `size` 次就处理完了一层。 ## 一句话总结 前中后序就是 `result.add` 放在递归调用的前面、中间还是后面;层序用队列一层一层处理。 --- 下一篇:[02 - 二叉树的最大深度](./02-max-depth.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入