94. 二叉树的中序遍历

难度：🟢 Easy | 标签：树、栈、递归 | 状态：⬜ LeetCode 链接

思路

中序 = 左 → 根 → 右。 迭代版用显式栈：一路压左子，弹出访问，再转右子。

代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        auto* cur = root;
        while (cur || !st.empty()) {
            while (cur) { st.push(cur); cur = cur->left; }
            cur = st.top(); st.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }
};

复杂度

• 时间 O(n)，空间 O(h)

易错 / 回顾

• 递归版更短但 O(h) 栈，迭代版同栈空间
• 前序：访问后压栈、先右后左
• 后序：双栈或单栈用 prev 标记
• Morris 遍历 O(1) 空间，进阶题再学