前序遍历是根→左→右，必须先访问节点再递归左右子树；中序遍历是左→根→右，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 性质时成立，和遍历算法本身无关。
容易被忽略的点：中序不是“从中间开始”，而是严格按左-根-右顺序深入。有人误以为要先找最左节点再往上回溯——其实递归自然完成该过程。
立即学习“C++免费学习笔记（深入）”；
- 递归左子树必须放在访问操作之前
- 若用于验证 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⁵ 层），递归会爆栈，此时必须改用迭代+显式栈，但那是另一类问题
递归写法简单直接，但它的“简单”建立在对调用时机的精确控制上——多一行位置错，遍历语义就全变了。
