17370845950

前序遍历是根→左→右，必须先访问节点再递归左右子树；中序遍历是左→根→右，BST中序结果升序；后序遍历是左→右→根，适合释放内存和求树高；三者仅visit位置不同，共用同一递归框架。

前序遍历（根→左→右）必须先访问再递归

前序遍历的核心是「访问当前节点 → 递归左子树 → 递归右子树」，顺序不能颠倒。一旦把 visit(node) 放到递归调用之后，就变成中序或后序了。

常见错误：在空指针检查前就调用 node->val，导致段错误。

• 务必先判 if (node == nullptr)，再访问成员
• 递归调用时传入 node->left 和 node->right，不是 node 自身
• 若需返回遍历结果（如 vector），建议用引用参数传入容器，避免频繁拷贝

void preorder(TreeNode* node, vector& res) {
    if (node == nullptr) return;
    res.push_back(node->val);      // 先访问
    preorder(node->left, res);     // 再递归左
    preorder(node->right, res);   // 最后递归右
}

中序遍历（左→根→右）天然适配 BST 排序输出

中序遍历对二叉搜索树（BST）有特殊意义：结果一定是升序排列。但这个性质只在树满足 BST 性质时成立，和遍历算法本身无关。

容易被忽略的点：中序不是“从中间开始”，而是严格按左-根-右顺序深入。有人误以为要先找最左节点再往上回溯——其实递归自然完成该过程。

• 递归左子树必须放在访问操作之前
• 若用于验证 BST，可在访问时检查 prev_val val，发现违反即标记非法
• 非递归中序需要手动模拟栈，但递归版本简洁可靠，无栈溢出风险（除非树深度极大）

void inorder(TreeNode* node, vector& res) {
    if (node == nullptr) return;
    inorder(node->left, res);     // 先递归左
    res.push_back(node->val);      // 再访问
    inorder(node->right, res);   // 最后递
归右
}

后序遍历（左→右→根）适合释放内存和求高度

后序是唯一一种左右子树都处理完才接触当前节点的遍历方式，因此天然适用于：释放以该节点为根的整棵子树、计算树高、判断平衡性等场景。

典型误用：把释放逻辑写成 delete node; preorder(node->left) —— 这会导致访问已释放内存，UB（未定义行为）。

• 必须先递归左右，最后才 delete node
• 求树高时，返回 1 + max(left_height, right_height)，空节点高为 0
• 若函数需返回值（如高度），就不能用 void，要改用 int 并注意空节点返回值

int getHeight(TreeNode* node) {
    if (node == nullptr) return 0;
    int leftH = getHeight(node->left);
    int rightH = getHeight(node->right);
    return 1 + max(leftH, rightH);  // 后序：子树高度已知，才能算当前
}

三个遍历共享同一套递归结构，差异仅在 visit 位置

前序、中序、后序本质是同一个 DFS 框架，只是 visit() 或等效操作（如 push_back、delete）插入的位置不同。强行记三套代码反而易错。

真正要注意的是：递归终止条件、空指针防护、以及是否需要返回值。比如求深度必须返回整数，而单纯打印可以 void；收集结果用引用传参比返回新容器更高效。

• 所有遍历都依赖 node == nullptr 判断，不可省略
• 递归调用语句顺序固定：left 在 right 前，这是约定，也是多数题目的隐含要求
• 若树深度超过系统栈限制（如 >10⁵ 层），递归会爆栈，此时必须改用迭代+显式栈，但那是另一类问题

递归写法简单直接，但它的“简单”建立在对调用时机的精确控制上——多一行位置错，遍历语义就全变了。