二叉树中序遍历的递归与迭代实现

如果不使用递归，计算机会怎么做？

第一性原理要求我们理解底层运作。递归在计算机底层是通过调用栈（Call Stack）实现的。

如果我们想用迭代（非递归）来实现，我们要问自己：

在处理左子树的过程中，我如何'记住'以后要回来处理当前的根节点和右子树？

我们需要一个物理容器来模拟这个记忆，这个容器就是栈（Stack）。栈的特性是'后进先出'，这完美契合了我们的需求：最后被路过的根节点，要先被处理（在处理完它的左子树后）。

迭代逻辑的重新推导：

1. 向左深钻： 只要有左孩子，我就一直往左走，并把路过的每一个'根节点'都扔进栈里。因为根据中序遍历，这些节点现在都不能处理，得等左边处理完。
2. 触底反弹： 当我走到最左边（遇到 nullptr）时，栈顶就是当前最左的节点。
3. 处理并转向： 弹出栈顶节点，记录它的值（这就是'根'），然后转向它的'右子树'，重复上述过程。

C++ 代码实现（迭代版）：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* curr = root;
        // 只要当前节点不为空，或者栈里还有没回溯完的节点
        while (curr != nullptr || !st.empty()) {
            // 步骤 1: 尽可能向左走，把路上的节点都'暂存'起来
            while (curr != nullptr) {
                st.push(curr);
                curr = curr->left;
            }
            // 步骤 2: 此时 curr 是空，说明左边走到底了。弹出最近的一个'根'
            curr = st.top();
            st.pop();
            // 步骤 3: 处理当前节点（左 -> 根）
            res.push_back(curr->val);
            // 步骤 4: 转向右子树（根 -> 右）
            curr = curr->right;
        }
        return res;
    }
};

面试回答

在面试中，面试官不仅看你的代码是否正确，更看重你解决问题的逻辑严密性和对计算机底层原理的理解。

你可以按照'定义解析 -> 递归推导 -> 迭代优化'的顺序，用一种类似'演化'的方式来讲授你的思路。以下是一个推荐的叙述话术：

第一步：拆解定义

'首先，我会从二叉树的物理结构出发。中序遍历的定义是'左子树 -> 根节点 -> 右子树'。

这意味着对于任何一个局部子树，我必须保证左侧的所有节点都被访问完，才能处理当前节点。这种局部与整体逻辑一致的特性，自然而然地让我联想到递归。'

第二步：由浅入深——递归解法

'在最底层逻辑上，我只需要定义一个递归函数：

1. 边界条件：如果节点为空，说明到底了，直接返回。
2. 递归单元：先递归调用左孩子，再记录当前节点的值，最后递归调用右孩子。

这是最符合直觉的解法，代码极其简洁，时间复杂度是 O(n)。'

第三步：硬核推演——迭代与栈

'如果面试官您希望探讨非递归的实现，那么我们需要思考计算机是如何处理递归的。

递归的本质是利用了系统的调用栈（Call Stack）。为了手动实现迭代，我们需要自己维护一个辅助栈 std::stack：

• 核心矛盾：我们一路向左走的时候，经过的'根节点'还不能处理，必须先存起来。
• 模拟过程：
  1. 我用一个 curr 指针模拟探索路径。只要 curr 不为空，我就把它压入栈中，然后拼命向左走。
  2. 当 curr 为空时，说明左边已经走到底了。此时，栈顶元素就是我们需要处理的'最左根节点'。
  3. 弹出栈顶，记录数值，然后将指针移向该节点的右孩子，重复这个循环。

这种方法在本质上是手动管理回溯路径，避免了递归带来的系统栈溢出风险。'

第四步：进阶对比

'最后，我会简单对比一下：

• 空间复杂度：在树极度不平衡（像个链表）时，递归和迭代的栈空间都是 O(n)。
• 面试亮点：如果对空间有极致要求，其实还有一种 Morris 遍历算法，利用叶子节点的空指针建立线索，可以将空间复杂度降到 O(1)，但它会暂时改动树的结构。'