递归遍历前中后序区别仅在于visit(root)位置：前序根左右、中序左根右、后序左右根；非递归中序用栈模拟，统一迭代法以nullptr标记访问时机。
递归实现前中后序遍历，核心就三个位置
前序、中序、后序的区别不在逻辑结构，而在 visit(root) 这句代码放在递归调用的哪个位置。只要记住：前序是“根左右”，中序是“左根右”，后序是“左右根”，对应到代码就是访问节点的时机不同。
假设二叉树节点定义为：
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};三种遍历的递归写法仅差一行顺序：
// 前序：根 → 左 → 右
void preorder(TreeNode* root, vector<int>& res) {
if (!root) return;
res.push_back(root->val); // ✅ 访问放最前
preorder(root->left, res);
preorder(root->right, res);
}
<p>// 中序：左 → 根 → 右
void inorder(TreeNode* root, vector<int>& res) {
if (!root) return;
inorder(root->left, res); // ✅ 先递归左
res.push_back(root->val); // ✅ 访问在中间
inorder(root->right, res);
}</p><p>// 后序：左 → 右 → 根
void postorder(TreeNode* root, vector<int>& res) {
if (!root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val); // ✅ 访问放最后
}非递归中序遍历最常用，栈模拟调用过程
面试和工程中更常考非递归写法，尤其是中序——它天然对应 BST 的升序输出。关键不是背模板，而是理解栈里存的是“待回溯的根节点”，每次弹出即表示“左子树已处理完，现在该访问自己了”。
立即学习“C++免费学习笔记（深入）”；
- 循环条件是
cur != nullptr || !stk.empty()，不能只判栈空 - 入栈动作必须在向左走之前做，否则会漏掉当前节点
- 每次从栈弹出后，立刻把
cur设为cur->right，进入右子树处理
vector<int> inorderIterative(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()) {
while (cur) {
stk.push(cur);
cur = cur->left; // 一路压左
}
cur = stk.top(); stk.pop();
res.push_back(cur->val); // 访问
cur = cur->right; // 切换到右子树
}
return res;
}统一迭代法：用 null 标记访问时机
想一套代码通吃三种遍历？可以，但代价是空间多存一倍指针。思路是把“该访问根节点”这个动作也压栈，用 nullptr 作为标记。遇到 nullptr 就说明下一个节点就是该被访问的根。
以前序为例（中/后序只需调整入栈顺序）：
- 入栈顺序：先
root->right，再nullptr，再root->left（保证左先出） - 遇到
nullptr时，下一个弹出的就是要访问的节点 - 注意：必须检查
!stk.empty()再取顶，否则运行时崩溃
vector<int> preorderUniform(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
if (root) stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top(); stk.pop();
if (node != nullptr) {
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
stk.push(node); // 根放最后
stk.push(nullptr); // 标记：下次该访问它
} else {
node = stk.top(); stk.pop();
res.push_back(node->val);
}
}
return res;
}层序遍历不属于 DFS，别混进前中后序里
题目问的是“前中后序”，本质是深度优先搜索（DFS）的三种访问顺序。而层序（BFS）用队列，逻辑完全不同：queue<treenode></treenode> + 每次取 q.size() 个节点处理一层。
容易踩的坑：
- 误以为“后序迭代 = 中序改两行”，其实后序非递归真正难点在于：必须确保右子树也遍历完了才能访问根——所以需要额外变量记录上次访问节点
- LeetCode 上
TreeNode默认构造函数可能不带初始化，left/right野指针导致 UBSAN 报错 - 返回值用
vector还是直接打印？接口要求决定是否需要传引用或返回新容器
真正难的不是写出来，是在边界 case（空树、单节点、只有左/右子树）下逻辑依然自洽。动手前先手画三节点树跑一遍指针流转，比硬背模板可靠得多。
