🌳 二叉树遍历入门：从中序遍历到层序与右视图
本文涵盖 LeetCode 上的三道基础但极具代表性的二叉树遍历题：
- 二叉树的中序遍历
- 二叉树的层序遍历
- 二叉树的右视图
通过这些题目，我们将从 DFS 到 BFS，深入理解如何处理树结构的不同维度信息。
🧩 题目一：94. 二叉树的中序遍历
📝 题目描述
给定一棵二叉树，返回它的中序遍历。
中序遍历顺序：左子树 → 根节点 → 右子树
💡 解题思路
中序遍历是深度优先搜索（DFS）中的一种经典形式。我们可以通过递归（最自然）或迭代（更贴近底层执行过程）两种方式来完成。
✅ 解法一：递归
func inorderTraversal(root *TreeNode) []int {
res := []int{
}
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)
res = append(res, node.Val)
dfs(node.Right)
}
dfs(root)
return res
}
🧠 思路总结
递归的核心是“做当前，交给子问题”，结构上非常清晰。
✅ 解法二：迭代（用栈模拟）
func inorderTraversal(root *TreeNode) []int {
res := []int{
}
stack := []*TreeNode{
}
curr := root
for curr != nil || len(stack) > 0 {
for curr != nil {
stack = append(stack, curr)
curr = curr.Left
}
curr = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, curr.Val)
curr = curr.Right
}
return res
}
📌 注意点：
- 用一个 while 循环控制整体流程。
- 用一个内嵌的 for 循环不断向左深入。
- 弹栈后处理当前节点，再转向右子树。
🧩 题目二：102. 二叉树的层序遍历
📝 题目描述
返回一个按层次遍历（每一层从左到右）的节点值数组。
💡 解题思路
层序遍历就是经典的广度优先搜索（BFS），借助队列来完成逐层访问。
✅ 解法：使用队列 BFS
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{
}
}
res := [][]int{
}
queue := []*TreeNode{
root}
for len(queue) > 0 {
level := []int{
}
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, level)
}
return res
}
📌 关键点：
- 使用
queue存储当前层的所有节点。 - 通过
size确定每层的边界。 - 每层遍历完成后将其加入结果集。
🧩 题目三：199. 二叉树的右视图
📝 题目描述
从右侧观察一棵二叉树，返回你能看到的节点值。
💡 解题思路
本质还是 BFS，只不过我们只关心每一层的最后一个节点。
✅ 解法：BFS + 每层最后一个节点
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{
}
}
res := []int{
}
queue := []*TreeNode{
root}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
queue = queue[1:]
if i == size-1 {
res = append(res, node.Val)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return res
}
📌 细节提示：
- 每层的最后一个节点
i == size - 1才加入结果。 - 和层序遍历一样，使用
queue来按层推进。
🧠 总结与反思
| 遍历类型 | 算法 | 数据结构 | 应用 |
|---|---|---|---|
| 中序遍历 | DFS | 栈 / 递归 | 搜索树性质、线索二叉树 |
| 层序遍历 | BFS | 队列 | 可视化结构、层级分析 |
| 右视图 | BFS | 队列 | 一层一个视角节点 |
- DFS 与 BFS 的思维方式差异是树结构的关键入门点。
- 掌握递归与迭代切换思维，对后续复杂结构建树、剪枝、遍历非常重要。
下一篇我们将探索如何通过遍历构造树结构（前序 + 中序 → 构造二叉树、数组 → 平衡搜索树等），敬请期待！
