BST插入的核心逻辑是找到满足left<root<right约束的空位置并挂载新节点；递归需返回新子树根以更新父指针，迭代需记录parent再赋值；插入不保证平衡。
插入操作的核心逻辑是什么
二叉搜索树（BST）插入的本质是：找到值该落脚的空位置，然后挂上去。不是递归或迭代本身重要，而是必须严格满足 left < root < right 的结构约束。一旦插错位置，整棵树就不再是 BST，后续查找、删除都会出错。
- 插入前必须从根开始比较，一路向下找“应该放哪”
- 遇到空指针（
nullptr）时才真正插入新节点，不能提前新建再比较 - 每次比较只决定往左还是往右，不修改当前节点内容
递归实现怎么写才不会漏掉返回值
C++ 里用递归插入，最常踩的坑是：忘了把子树的新根返回给父节点更新指针。因为 C++ 默认传值，root->left = insert(root->left, val) 这一步不可省——哪怕 root->left 原来是 nullptr，也得靠赋值把新节点链上去。
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);
return root;
}- 函数必须返回
TreeNode*，调用方要用它更新左右指针 - 不要写成
void insert(...)然后试图通过引用传参绕过——容易混淆所有权且不直观 - 如果根节点为空，直接返回新节点；否则递归后一定返回当前 root，保证上层能接住
迭代实现要注意指针的双重身份
迭代法不用函数调用栈，但得手动维护“当前节点”和“父节点”两个角色。常见错误是：只移动 cur，却没记住它从哪来，导致最后找不到地方挂新节点。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 必须用一个额外指针（比如
parent）记录上一个非空节点 - 循环中只负责导航，真正插入发生在循环结束后，靠
parent->left或parent->right赋值 - 别在循环里直接
new，否则可能覆盖已有子树
TreeNode* insert(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
TreeNode* cur = root;
TreeNode* parent = nullptr;
while (cur) {
parent = cur;
if (val < cur->val) cur = cur->left;
else cur = cur->right;
}
if (val < parent->val) parent->left = new TreeNode(val);
else parent->right = new TreeNode(val);
return root;
}插入后树还平衡吗？要不要调整
标准 BST 插入不保证平衡。连续插入升序数据（如 1,2,3,4,5）会退化成链表，查找变成 O(n)。但这是设计使然，不是 bug。
立即学习“C++免费学习笔记（深入）”；
-
insert函数本身不负责旋转或重平衡 - 如果需要 O(log n) 性能，得换用 AVL 树或红黑树，它们在插入后自动调用
rotateLeft/rotateRight或染色 - 单纯 BST 实现里加平衡逻辑，会大幅增加复杂度，且和“插入”职责混在一起，不推荐初学时硬套
实际编码时，先确保插入逻辑正确、指针链接无误，再考虑是否引入平衡机制。很多场景下，BST 本就不追求绝对平衡，而是侧重语义正确性。
