LeetCode 94. 二叉树的中序遍历

约 3 分钟
文章信息 23 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 需复习 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 小米 虾皮 小红书 LeetCode 热题 100
标签
深度优先搜索 树 二叉树 栈 中序遍历
目录

题目描述

✅ 94. 二叉树的中序遍历

image-20230305164849556

题意分析

给定一棵二叉树的根节点，要求按「中序」返回所有节点值组成的列表。中序的定义是固定的：先访问左子树、再访问根节点、最后访问右子树，即「左 → 根 → 右」。

约束信号很温和：节点数最多 100，值域也很小，任何线性做法都绰绰有余。真正的考点写在进阶里——递归解法很平凡，题目明确要求你给出迭代版本，这才是面试官想看的部分。

边界上要注意：空树应返回空列表而不是 null；单节点树返回只含根值的列表；退化成一条链的树也必须能正确处理，它会把辅助空间推到最坏情况。

解法：栈模拟递归中序遍历

核心思路

中序遍历的顺序是“左子树 → 根节点 → 右子树”。使用栈保存尚未访问的祖先节点：先不断沿左孩子入栈，走到空节点后弹出栈顶并记录，再转向它的右子树。

cur 表示当前要处理的节点，栈表示左子树尚未处理完的祖先链。

解题步骤

  • 初始化结果列表、空栈和 cur = root。
  • 将 cur 及其左链依次入栈。
  • 左侧走到尽头后，弹出栈顶并记录节点值。
  • 将 cur 指向该节点的右孩子，重复以上过程，直到 cur 为空且栈也为空。

代码实现

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = 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();
            ans.add(cur.val);
            cur = cur.right;
        }
        return ans;
    }
}

func inorderTraversal(root *TreeNode) []int {
    ans := []int{}
    stack := []*TreeNode{}
    cur := root

    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        ans = append(ans, cur.Val)
        cur = cur.Right
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点入栈、出栈各一次。
  • 空间复杂度：$O(h)$，h 为树高；最坏为 $O(n)$。

关键点总结

  • 节点入栈时不访问，出栈时才记录其值。
  • 外层循环必须同时检查 cur 和栈，二者都为空才结束。
  • 转向右子树后，会用相同流程处理其左链。

易错点总结

  • 只以 cur != null 作为循环条件，会漏掉栈中尚未访问的节点。
  • 入栈时记录节点值，会写成前序遍历。
  • 弹栈后忘记转向右孩子，会重复访问或漏掉右子树。
  • Go 弹栈时只读取栈顶却不缩短切片，会导致死循环。

相似题目

题目 难度 考察点
144. 二叉树的前序遍历 简单 同一栈框架，访问时机提前到入栈时
145. 二叉树的后序遍历 简单 需记录右子树是否访问过，三种遍历中迭代最难
589. N 叉树的前序遍历 简单 推广到多叉：孩子需逆序入栈保证顺序
590. N 叉树的后序遍历 简单 多叉后序等于「根右到左的前序」再整体反转
173. 二叉搜索树迭代器 中等 把中序迭代拆成 next/hasNext，栈状态跨调用保存
230. 二叉搜索树中第 K 小的元素 中等 利用 BST 中序有序性，遍历到第 $k$ 个即提前终止