C++ 怎么实现二叉树遍历 C++ 前序中序后序递归写法【树】

前序遍历先访问根再递归左右子树，需判空；中序遍历左根右，天然升序，常用于验证BST；后序遍历左右根，适用于依赖子树结果的场景如求树高。

前序遍历：根→左→右，递归函数怎么写

核心就是访问当前节点后，立刻递归左子树、再递归右子树。注意空指针必须提前检查，否则会崩溃。

• nullptr 判定不能少，C++ 中对空指针调用 ->val 或进入递归是未定义行为
• 顺序不能错：先处理 root->val，再 preorder(root->left)，最后 preorder(root->right)
• 如果要收集结果，传引用 vector& res 比返回新 vector 更高效

示例片段：

void preorder(TreeNode* root, vector& res) {
    if (!root) return;
    res.push_back(root->val);      // 根
    preorder(root->left, res);     // 左
    preorder(root->right, res);    // 右
}

中序遍历：左→根→右，为什么常用来验证 BST

中序遍历天然产生升序序列（对二叉搜索树而言），所以常被用于 isValidBST 的实现。递归逻辑看似只换了个顺序，但语义完全不同。

• 必须严格按「左→根→右」执行，中间不能跳过空节点的判断
• 若用于验证 BST，可在递归中维护一个 long long prev = LLONG_MIN，每次访问节点前比较 root->val
• 注意整型溢出风险：用 long long 或 TreeNode* 记录上一节点更安全

关键代码段：

立即学习“C++免费学习笔记（深入）”；

XPaper Ai

AI撰写论文、开题报告生成、AI论文生成器尽在XPaper Ai论文写作辅助指导平台

下载

void inorder(TreeNode* root, vector& res) {
    if (!root) return;
    inorder(root->left, res);      // 左
    res.push_back(root->val);      // 根
    inorder(root->right, res);     // 右
}

后序遍历：左→右→根，什么场景非用它不可

需要子树信息才能处理父节点时，必须用后序，比如计算树高、释放内存、求最大路径和。它的递归栈深度和前/中序一致，但访问时机最晚。

• 左右子树必须都完成递归，才能处理当前节点——这是和前/中序的本质区别
• 释放内存时，必须先 delete 左右子节点，再 delete root，否则悬垂指针
• 返回值类型常为 int 或 pair，而非单纯收集值

典型用法：

int postorderHeight(TreeNode* root) {
    if (!root) return 0;
    int lh = postorderHeight(root->left);
    int rh = postorderHeight(root->right);
    return max(lh, rh) + 1;  // 左右都算完，才更新当前高度
}

递归终止条件和参数传递容易踩的三个坑

这三个点不注意，编译可能通过，但运行时崩溃或结果错乱。

• 忘记判 if (!root) → 直接解引用 nullptr，触发 Segmentation fault
• 传参用值传递 vector res 而非引用 → 每层递归操作副本，最终 res 为空
• 误把 root->left 写成 root->right（尤其在中序里）→ 序列完全错乱，且不易一眼发现

调试时可加一句 cout val 快速验证访问顺序是否符合预期。递归本身不难，但指针和边界稍有松动就会连锁出错。