二叉树的中序遍历

这段代码实现了二叉树的中序遍历（In-order Traversal），采用的是**非递归（迭代）**的方法。

中序遍历的逻辑顺序是：左子树 -> 根节点 -> 右子树。在迭代实现中，我们利用**栈（Stack）**来模拟递归时的函数调用栈，帮助我们在访问完左子树后“回退”到父节点。

1. 代码逐行注释

C++

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; // 存储遍历结果的数组 stack<TreeNode*> stk; // 辅助栈，用于暂存父节点，以便处理完左子树后能回来 // 循环条件：节点不为空（表示还有子树没钻到底）或者 栈不为空（表示还有父节点没处理） while (root != nullptr || !stk.empty()) { // --- 步骤 1: 一路向左狂奔 --- while (root != nullptr) { stk.push(root); // 将当前节点入栈（因为待会儿处理完左边还要回来找它） root = root->left; // 继续向左子节点移动 } // --- 步骤 2: 触底反弹，处理节点 --- root = stk.top(); // 从栈顶取出最近的一个“左尽头”节点 stk.pop(); // 弹出已取出的节点 res.push_back(root->val); // 【核心】访问当前节点（即中序遍历中的“根”） // --- 步骤 3: 转向右子树 --- // 既然当前节点和它的左子树都处理完了，接下来按顺序该看它的右子树了 root = root->right; } return res; // 返回最终的中序序列 } };

2. 核心思路分析

这个算法的核心在于**“先压后取”**：

1. 左钻到底：中序遍历要求最先访问左下角的节点。通过while(root != nullptr)，我们将沿途的所有节点都压入栈中。这些节点此时都在等待它们的左子树处理完毕。

2. 栈的作用：栈在这里起到了“记事本”的作用。当我们走到最左边的叶子节点（nullptr）时，栈顶存储的就是该空节点的父节点。

3. 转向右侧：一旦从栈中弹出一个节点并记录了它的值，说明该节点的左边已经全部搞定。根据左 -> 根 -> 右的规则，下一步必须移动到root->right。如果右孩子存在，它会重复“左钻到底”的过程；如果右孩子不存在，下一次循环会直接从栈中弹出更高层的父节点。

3. 运行示例

假设有一棵树如下：

1 \ 2 / 3

1. 开始：root指向 1。栈为空。

2. 第一步：1 入栈，root移向 1 的左边（nullptr）。

3. 第二步：栈不空，弹出 1，res = [1]。root移向 1 的右边（节点 2）。

4. 第三步：2 入栈，root移向 2 的左边（节点 3）。

5. 第四步：3 入栈，root移向 3 的左边（nullptr）。

6. 第五步：弹出 3，res = [1, 3]。root移向 3 的右边（nullptr）。

7. 第六步：弹出 2，res = [1, 3, 2]。root移向 2 的右边（nullptr）。

8. 结束：栈空且root为空，返回结果。