LeetCode 94. 二叉树的中序遍历

◎

本节目标

用指针与显式栈持续压入左链，按左、根、右顺序访问。

这道题承接遍历与层序视角：当前节点必须在左子树完成后、右子树开始前访问。空树不需要压栈，直接返回空序列。

查看 LeetCode 原题

朴素思路与瓶颈

递归会沿左孩子不断深入，回程时访问根并转向右孩子。若只把根入栈一次，无法记住整条尚未访问的祖先左链，因此迭代写法必须持续压栈。

核心不变量

cur 指向下一条尚未压入的左链；栈从底到顶保存已到达但左子树尚未全部完成的节点。左链压尽后，栈顶节点的左子树已经完成，弹出并访问它，再令 cur 指向其右孩子。

正确性依据

内层循环先把当前子树最左的路径全部入栈，所以首次弹出的一定没有未访问左子树。每次访问节点后只转向其右子树，并重复同一过程。因此任一节点都严格在左子树之后、右子树之前输出，得到中序序列。

代码实现

C++

C++17

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> answer;
        std::stack<TreeNode*> nodes;
        TreeNode* cur = root;

        while (cur != nullptr || !nodes.empty()) {
            while (cur != nullptr) {
                nodes.push(cur);
                cur = cur->left;
            }
            cur = nodes.top();
            nodes.pop();
            answer.push_back(cur->val);
            cur = cur->right;
        }
        return answer;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        answer: list[int] = []
        nodes: list[TreeNode] = []
        cur = root

        while cur is not None or nodes:
            while cur is not None:
                nodes.append(cur)
                cur = cur.left
            cur = nodes.pop()
            answer.append(cur.val)
            cur = cur.right
        return answer

复杂度分析

每个节点至多入栈和出栈一次，时间复杂度为 O(n)。栈最多保存树高个节点，空间复杂度为 O(h)。

易错点

• 内层循环只压入一个左孩子，遗漏更深的左链。
• 弹栈后没有将 cur 移到右孩子，导致右子树缺失。
• 仅在 cur 非空时循环，忽略栈中等待访问的祖先。

模式迁移

在二叉搜索树中，中序访问顺序严格递增；把访问计数加到这里，就能在第 k 次弹栈时提前停止。