LeetCode 701. 二叉搜索树中的插入操作
题目描述
题意分析
向给定二叉搜索树中插入一个新值
val，返回插入后的整棵树的根节点。插入后要保留原有节点，并继续满足每个节点左子树值更小、右子树值更大的搜索树性质。题目保证新值在原树中不存在，原节点值也互不相同。输入可能为空；结果的树形不要求唯一，只要包含新增值并保持搜索树性质即可。因此可以选择沿搜索路径把新值作为叶子接入，不需要调整原有树形。
解法：沿搜索路径迭代插入
核心思路
[!blue]
查找某个值时，若它小于当前节点，就只能继续找左子树；大于当前节点，就只能找右子树。插入也可以沿同一条路径前进，直到目标方向没有孩子，这个空位置就是可以接入新节点的地方。
每次向左，都会增加“新值小于当前祖先”的限制；每次向右，则增加“新值大于当前祖先”的限制。路径选择本身已经逐一满足这些比较，因此到达空位置时，新值既符合直接父节点的大小要求，也符合之前所有祖先留下的约束。新节点没有孩子，不会影响原树其他节点之间的关系。
实现时让游标停在父节点上检查孩子：目标方向已有孩子就继续下移，没有孩子就把新节点赋给该孩子字段。仅仅走到空引用后给局部变量赋一个新节点，并没有修改父节点的连接，树中不会真正多出它。
非空树用独立游标
node移动，保留最初的root用于返回。新节点接好后立即结束循环；因为新值不存在，有限的搜索路径一定会遇到缺失孩子，不会一直查找下去。空树没有父节点可接，直接创建并返回一个节点，作为新的根。
解题步骤
- 根为空时，创建包含
val的节点并直接返回。- 否则令游标
node = root。- 新值较小时检查左孩子：为空就接入新节点并结束，否则进入左孩子。
- 新值较大时对右孩子进行相同处理；题目保证不会出现等于现有值的情况。
- 插入完成后返回原
root，保留整棵树的入口。
代码实现
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
// 独立游标保留原根，比较路径继承祖先边界
TreeNode node = root;
while (true) {
if (val < node.val) {
if (node.left == null) {
// 通过父节点接入缺失孩子，而非只修改局部引用
node.left = new TreeNode(val);
break;
}
node = node.left;
} else {
if (node.right == null) {
node.right = new TreeNode(val);
break;
}
node = node.right;
}
}
return root;
}
}
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{Val: val}
}
// 独立游标保留原根，比较路径继承祖先边界
node := root
for {
if val < node.Val {
if node.Left == nil {
// 通过父节点接入缺失孩子，而非只修改局部引用
node.Left = &TreeNode{Val: val}
break
}
node = node.Left
} else {
if node.Right == nil {
node.Right = &TreeNode{Val: val}
break
}
node = node.Right
}
}
return root
}
复杂度分析
- 时间复杂度：$O(h + 1)$，
h为原树高度，只沿一条搜索路径移动并创建一个节点。平衡树的查找为 $O(\log n)$，退化树最坏为 $O(n)$，空树直接用常数时间处理。- 空间复杂度：$O(1)$，迭代过程只保存游标，且只新增一个必要的树节点。
关键点总结
[!green]
- 插入位置由搜索路径决定，沿途比较自然保留全部祖先约束。
- 新节点必须接到父节点的孩子字段上，改变局部引用不等于改变树。
- 游标与返回入口分开，空树直接返回新根，非空树接好后返回原根。
易错点总结
[!yellow]
- 把
root一直当作游标向下改写，最后返回的就只是树中的某棵子树。- 找到空位置后仅创建局部节点，未写回父节点的孩子字段，新节点不会接入原树。
- 插入完成后继续循环，可能在新节点处重复处理同一个值，无法按预期结束。
- 没有单独处理空根，直接读取根值会发生空引用错误。
- 只比较最后的父子关系却随意选择插入位置，可能违反更早祖先限制；应沿完整搜索路径定位。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 700. 二叉搜索树中的搜索 | 简单 | 复用BST查找路径，查到应该出现但为空的位置后创建新节点。 |
| 450. 删除二叉搜索树中的节点 | 中等 | 同样先按有序关系定位值，删除还需处理两个孩子及替代节点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！