【LeetCode 热题100】二叉树遍历入门：从中序遍历到层序与右视图（力扣94 / 102/199）（Go语言版）

🌳 二叉树遍历入门：从中序遍历到层序与右视图

本文涵盖 LeetCode 上的三道基础但极具代表性的二叉树遍历题：

• 94. 二叉树的中序遍历
• 102. 二叉树的层序遍历
• 199. 二叉树的右视图

通过这些题目，我们将从 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 := rootfor 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 的思维方式差异是树结构的关键入门点。
• 掌握递归与迭代切换思维，对后续复杂结构建树、剪枝、遍历非常重要。

---

下一篇我们将探索如何通过遍历构造树结构（前序 + 中序 → 构造二叉树、数组 → 平衡搜索树等），敬请期待！