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

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