插入节点必须用指针引用或二级指针，因C++默认值传递会使修改仅作用于副本，无法更新父节点left/right；查找为O(h)而非O(log n)，因树高h可能退化为n；递归插入简洁但有栈溢出风险，非递归更安全；构造节点须显式初始化左右指针为nullptr，避免野指针引发未定义行为。
插入节点时为什么必须用指针的引用或二级指针
因为 C++ 函数参数默认按值传递，如果只传 TreeNode*，函数内部修改的是副本，无法真正改变父节点的 left 或 right 指针。常见错误是写成 void insert(TreeNode* root, int val)，结果插入后树根没变、子树挂不上。
正确做法是传引用：void insert(TreeNode*& root, int val)，或用二级指针：void insert(TreeNode** root, int val)。前者更直观，后者在某些边界（如空树初始化）逻辑更统一。
示例关键片段：
void insert(TreeNode*& root, int val) {
if (!root) {
root = new TreeNode(val); // 直接改父节点的指针
return;
}
if (val < root->val)
insert(root->left, val);
else
insert(root->right, val);
}查找操作为何能保证 O(h) 时间但不一定是 O(log n)
二叉搜索树的查找依赖于「左小右大」性质，每次比较后只需进入一个子树，所以单次查找最多走 h 步（h 是树高）。但 h 不一定等于 log₂n —— 如果插入序列本身有序（如 1,2,3,4,5），树会退化成链表，h = n，查找退化为 O(n)。
立即学习“C++免费学习笔记（深入）”；
这意味着：BST 的查找效率取决于树的平衡性，而非单纯靠「二分」直觉。实际工程中若需稳定性能，得上 AVL 或红黑树；纯练手实现 BST 时，务必注意测试退化 case。
查找函数通常返回 TreeNode*，找不到就返回 nullptr：
TreeNode* search(TreeNode* root, int val) {
if (!root || root->val == val) return root;
return val < root->val ? search(root->left, val) : search(root->right, val);
}递归插入和非递归插入的取舍点在哪里
递归写法简洁、符合 BST 的自然定义，但有栈溢出风险（极端不平衡时深度达数万）；非递归版本用循环+指针跟踪父节点，空间复杂度 O(1)，适合生产环境或嵌入式场景。
非递归插入的关键是：必须提前保存父节点指针，否则找到空位时已丢失挂载位置：
- 用
TreeNode* cur = root遍历定位插入点 - 用
TreeNode* parent = nullptr记录上一个非空节点 - 循环结束后，根据
val和parent->val判断插在左还是右
注意：空树时要单独处理 root = new TreeNode(val)，不能依赖 parent。
为什么构造节点时建议显式初始化左右指针为 nullptr
如果不初始化，new TreeNode(val) 中的 left 和 right 是未定义值（野指针），后续判空 if (!root->left) 可能误判为真，导致段错误或逻辑错乱。尤其在调试优化开启时更易暴露。
推荐写法（C++11 起）：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};漏掉初始化是新手最常踩的坑之一，且问题不总立即显现，容易拖到集成测试才爆发。
