17370845950

递归遍历前中后序区别仅在于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& res) {
    if (!root) return;
    res.push_back(root->val);  // ✅ 访问放最前
    preorder(root->left, res);
    preorder(root->right, res);
}
// 中序：左 → 根 → 右
void inorder(TreeNode* root, vector& res) {
if (!root) return;
inorder(root->left, res);   // ✅ 先递归左
res.push_back(root->val);    // ✅ 访问在中间
inorder(root->right, res);
}
// 后序：左 → 右 → 根
void postorder(TreeNode* root, vector& res) {
if (!root) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);    // ✅ 访问放最后
}

非递归中序遍历最常用，栈模拟调用过程

面试和工程中更常考非递归写法，尤其是中序——它天然对应 BST 的升序输出。关键不是背模板，而是理解栈里存的是“待回溯的根节点”，每次弹出即表示“左子树已处理完，现在该访问自己了”。

• 循环条件是 cur != nullptr || !stk.empty()，不能只判栈空
• 入栈动作必须在向左走之前做，否则会漏掉当前节点
• 每次从栈弹出后，立刻把 cur 设为 cur->right，进入右子树处理

vector inorderIterative(TreeNode* root) {
    vector res;
    stack 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 preorderUniform(TreeNode* root) {
    vector res;
    stack 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 + 每次取 q.size() 个节点处理一层。

容易踩的坑：

• 误以为“后序迭代 = 中序改两行”，其实后序非递归真正难点在于：必须确保右子树也遍历完了才能访问根——所以需要额外变量记录上次访问节点
• LeetCode 上 TreeNode 默认构造函数可能不带初始化，left/right 野指针导致 UBSAN 报错
• 返回值用 vector 还是直接打印？接口要求决定是否需要传引用或返回新容器

真正难的不是写出来，是在边界 case（空树、单节点、只有左/右子树）下逻辑依然自洽。动手前先手画三节点树跑一遍指针流转，比硬背模板可靠得多。