什么是递归，什么是迭代！
刚刚学的层层嵌套，就是递归（我感觉更直观些）
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)：
计算机看到
5 + sum_recursive(4)，它必须先去算sum_recursive(4)。于是它暂停当前的计算（在内存里记下“这里有个 5 等着加”），去算
sum_recursive(4)。算
sum_recursive(4)时，看到4 + sum_recursive(3)，又暂停，去算sum_recursive(3)……直到算到
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; } };