什么是递归什么是迭代刚刚学的层层嵌套就是递归我感觉更直观些forwhile循环就是迭代。数学代码对比绝对简单我们算一个超级简单的数学题求 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开始逐层回头123336641010515。前序遍历核心规则死记这一句前序遍历顺序是中 - 左 - 右先处理根再处理左最后处理右在迭代法中为了实现“先左后右”入栈时必须反着来先压入右孩子再压入左孩子。因为栈Stack是后进先出LIFO——后放进去的先拿出来。为了让左孩子先被拿出来处理就必须让左孩子最后放进去。放根 ➡️ 取根记录 ➡️ 放右 ➡️ 放左class Solution { public: vectorint preorderTraversal(TreeNode* root) { stackTreeNode* st; vectorint 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: vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* 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: vectorint postorderTraversal(TreeNode* root) { stackTreeNode* st; vectorint 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; } };
