LeetCode 94. 二叉树的中序遍历

Categories:

Tags:

题目描述
思路分析
1. 解法一：迭代（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 94. 二叉树的中序遍历

思路分析

解法一：迭代（推荐）

核心思路：

中序遍历顺序为：左子树 → 根节点 → 右子树。迭代实现用显式栈模拟递归调用栈：

维护指针 cur 和空栈 stack，初始 cur 指向根节点。

循环：将 cur 沿左链一路压栈，直到 cur 为空。

弹出栈顶节点，访问其值，然后令 cur 转向其右子树。

重复上述过程，直到栈为空且 cur 为空。

BST 的中序遍历结果是严格递增序列，这是 BST 最重要的性质之一。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，每个节点恰好被访问一次。

空间复杂度：O(h)，其中 h 为二叉树的高度，最坏情况下退化为 O(n)。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = 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();
            res.add(cur.val);
            // 转向右子树
            cur = cur.right;
        }
        return res;
    }
}

func inorderTraversal(root *TreeNode) []int {
    var res []int
    var 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]
        res = append(res, cur.Val)
        // 转向右子树
        cur = cur.Right
    }

    return res
}

解法二：递归

核心思路：

递归实现最为简洁，直接按照中序遍历定义展开：

递归遍历左子树。

访问根节点（将值加入结果列表）。

递归遍历右子树。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树的节点数，每个节点恰好被访问一次。

空间复杂度：O(h)，其中 h 为二叉树的高度，即递归调用栈的深度，最坏情况下退化为 O(n)。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        // 递归遍历左子树
        dfs(node.left, res);
        // 访问根节点
        res.add(node.val);
        // 递归遍历右子树
        dfs(node.right, res);
    }
}

func inorderTraversal(root *TreeNode) []int {
    var res []int

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        // 递归遍历左子树
        dfs(node.Left)
        // 访问根节点
        res = append(res, node.Val)
        // 递归遍历右子树
        dfs(node.Right)
    }

    dfs(root)
    return res
}

相似题目

题目	难度	考察点
144. 二叉树的前序遍历	简单	二叉树、DFS
145. 二叉树的后序遍历	简单	二叉树、DFS
102. 二叉树的层序遍历	中等	BFS
98. 验证二叉搜索树	中等	中序遍历、DFS
538. 把二叉搜索树转换为累加树	中等	反向中序遍历
230. 二叉搜索树中第 K 小的元素	中等	中序遍历
173. 二叉搜索树迭代器	中等	迭代、栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/62975418