前序遍历核心是根→左→右：先访问根节点，再递归左子树，最后递归右子树；中序遍历为左→根→右，BST下天然升序；后序遍历是左→右→根，适用于释放内存、求高度等需子树结果的场景。
前序遍历：根→左→右，递归函数怎么写
核心是顺序控制：先访问当前节点，再递归左子树，最后递归右子树。注意空指针必须提前返回，否则会崩溃。
-
root为nullptr时直接return，这是所有递归遍历的底线防护 - 访问操作（比如打印）必须放在递归调用之前
- 左右子树递归顺序不能颠倒，否则就不是前序了
void preorder(TreeNode* root) {
if (!root) return;
std::cout << root->val << " "; // 根
preorder(root->left); // 左
preorder(root->right); // 右
}
中序遍历：左→根→右，为什么输出是升序的
中序遍历天然适配二叉搜索树（BST）的有序性——只要树本身满足 BST 性质（左子树所有值
- 关键在于访问操作夹在两次递归之间：先左、再自己、最后右
- 如果你发现输出乱序，先检查树是不是 BST，而不是怀疑遍历逻辑
- 不要试图在递归里“排序”输出，那说明建树或需求理解有偏差
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left); // 左
std::cout << root->val << " "; // 根
inorder(root->right); // 右
}
后序遍历：左→右→根，哪些场景非它不可
后序最典型用途是释放树内存、计算子树高度、判断平衡性——因为必须等左右子树都处理完，才能安全操作当前节点。
- 访问操作必须放在最后，否则无法获取子树返回值（比如高度）
- 若用于析构，务必确保子节点指针置为
nullptr或立即delete，避免悬空指针 - 常见错误：把
delete root放在递归调用前，导致子树还没释放就被父节点删掉
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left); // 左
postorder(root->right); // 右
std::cout << root->val << " "; // 根（或 delete root;）
}
递归遍历统一要注意的三个坑
- 所有遍历函数参数必须是
TreeNode*，传值或传引用都会出错；尤其别写成 TreeNode（对象拷贝会崩溃）
- 没有返回值的遍历函数无法直接收集结果；如需存到
std::vector<int></int>，得加引用参数或改用返回 vector 的版本
- 递归深度大时（比如退化成链表的树），可能栈溢出；生产环境要考虑迭代写法或手动模拟栈
TreeNode*，传值或传引用都会出错；尤其别写成 TreeNode（对象拷贝会崩溃）std::vector<int></int>，得加引用参数或改用返回 vector 的版本实际用的时候，别光盯着“怎么写”，先想清楚：你要的是打印、收集、修改，还是释放？动作位置一变，遍历类型就得跟着变。
立即学习“C++免费学习笔记（深入）”；
