学完递归，学二叉树的迭代遍历

什么是递归，什么是迭代！

刚刚学的层层嵌套，就是递归（我感觉更直观些）

for，while循环，就是迭代。

数学代码对比（绝对简单）

我们算一个超级简单的数学题：求 1 + 2 + 3 + ... + n 的和。

写法一：迭代（循环，自己控制进度）

int sum_iterative(int n) { int result = 0; for (int i = 1; i <= n; i++) { // 我用 i 手动控制当前走到哪了 result = result + i; } return result; }

计算机在干嘛？它只负责重复执行大括号里的代码。没有任何“暂停”和“回头”，一路加到 n 结束。

写法二：递归（函数调自己，系统帮你暂停）

int sum_recursive(int n) { if (n == 1) return 1; // 停止条件 return n + sum_recursive(n - 1); // 在这里暂停！ }

计算机在干嘛？假设你调用sum_recursive(5)：

1. 计算机看到5 + sum_recursive(4)，它必须先去算sum_recursive(4)。

2. 于是它暂停当前的计算（在内存里记下“这里有个 5 等着加”），去算sum_recursive(4)。

3. 算sum_recursive(4)时，看到4 + sum_recursive(3)，又暂停，去算sum_recursive(3)……

4. 直到算到sum_recursive(1) = 1，开始逐层回头：1+2=3，3+3=6，6+4=10，10+5=15。

前序遍历：

核心规则（死记这一句）

前序遍历顺序是：中 -> 左 -> 右（先处理根，再处理左，最后处理右）

在迭代法中，为了实现“先左后右”，入栈时必须反着来：先压入右孩子，再压入左孩子。

因为栈（Stack）是后进先出（LIFO）——后放进去的先拿出来。为了让左孩子先被拿出来处理，就必须让左孩子最后放进去。

放根 ➡️ 取根（记录） ➡️ 放右 ➡️ 放左

class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> result; if (root == NULL) return result; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); // 中 st.pop(); result.push_back(node->val); if (node->right) st.push(node->right); // 右（空节点不入栈） if (node->left) st.push(node->left); // 左（空节点不入栈） } return result; } };

接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。

中序遍历（迭代法）

• 中序是：一路向左，入栈存；无路可走，出栈记；转向右边，再来一次。

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != NULL || !st.empty()) { if (cur != NULL) { // 指针来访问节点，访问到最底层 st.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据） st.pop(); result.push_back(cur->val); // 中 cur = cur->right; // 右 } } return result; } };

后序遍历

把前序左右翻一下，就是中右左，反着输出就是左右中。

class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> result; if (root == NULL) return result; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); result.push_back(node->val); if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈） if (node->right) st.push(node->right); // 空节点不入栈 } reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了 return result; } };