LeetCode 701. 二叉搜索树中的插入操作

2023-06-26 HGNULB 约 5 分钟

文章信息 11 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 5-10 字节跳动微软快手腾讯猿辅导百度

题目描述

✅ 701. 二叉搜索树中的插入操作

题意分析

输入是一棵满足「左子树全部小于根、右子树全部大于根」这一有序性质的二叉树，以及一个待插入的整数；要求把它放进树里，使得插入后整棵树仍然保持同一条有序性质，并返回新树的根。

题目额外说明了两点：待插入的值一定不在原树中，所以不必考虑「已存在」时该怎么办；以及只要结果树合法即可，不要求树形唯一，也不要求保持平衡，这意味着不需要旋转、不需要重建，任何一种合法摆放都能通过。

有序性质本身就把可行的落点框死了：从根出发，比当前节点小就只能落进左子树，比当前节点大就只能落进右子树，一路走到某个方向为空的位置。换句话说，如果坚持「不改动任何已有节点的连边」，落点是唯一的——就是查找这个值时会停下的那个空位。

节点数上界是 $10^4$，值域是 $-10^8$ 到 $10^8$，说明不必担心整数溢出，也说明一次沿路径下行的代价完全可以接受。

边界情形有两类：原树为空，此时新节点自己就是根，返回值不再是传入的指针；以及新值比树中所有值都小或都大，此时会一路走到最左端或最右端的叶子。若树本身退化成一条链，这条路径的长度就等于节点数。

解法：沿搜索路径迭代插入

核心思路

二叉搜索树已经给出了新值的唯一搜索方向：小于当前节点就进入左子树，大于当前节点就进入右子树。题目保证新值不存在，因此不需要处理相等分支。

可以把插入理解成一次“失败的查找”。沿搜索路径向下，第一次遇到的空孩子就是插入位置；把新节点挂上去只新增一条边，不会改变其他节点间的大小关系。

循环不变量是：游标 node 指向的子树一定包含新值的合法插入位置。比较后进入对应子树，不变量继续成立；若对应孩子为空，挂接后该节点同时满足祖先约束和父节点约束，所以整棵树仍是二叉搜索树。

解题步骤

若 root 为空，直接创建并返回新节点。

用 node 从根开始向下查找。

当 val < node.val 时检查左孩子；为空就挂到左边，否则继续走左子树。

当 val > node.val 时对右孩子做同样处理。

挂接完成后返回原来的根；非空树插入不会改变根节点。

例如向 [4, 2, 7, 1, 3] 插入 5：依次比较得到 5 > 4、5 < 7，而 7 的左孩子为空，所以把 5 挂在该位置。

代码实现

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)$，其中 $h$ 为树高。平衡树中是 $O(\log n)$，退化成链表时最坏是 $O(n)$。

空间复杂度：$O(1)$，迭代过程只使用一个游标；新建的结果节点不计入额外空间。

关键点总结

BST 插入就是沿查找路径找到第一个空孩子，不需要中序遍历或重建树。

在父节点处检查孩子是否为空，才能直接完成挂接。

迭代写法避免 $O(h)$ 的递归调用栈，尤其适合可能退化的树。

题目保证值不重复；若没有该保证，必须先约定重复值放置规则或拒绝插入。

易错点总结

空树时仍进入循环，会立即访问空指针；新节点应直接作为根返回。

只让游标走到 null 却没有保留父节点，最终无法挂接新节点。

比较方向写反会破坏 BST 的有序性；左子树必须更小，右子树必须更大。

插入完成后继续循环，可能重复插入或造成死循环，应立即结束。

把平均复杂度直接写成 $O(\log n)$ 不严谨；只有树高受控时才成立。

相似题目

题目	难度	考察点
700. 二叉搜索树中的搜索	简单	只走同一条查找路径但不修改结构，是本题去掉挂接步骤后的子问题
450. 删除二叉搜索树中的节点	中等	找到目标后还要处理双孩子节点的顶替，落点不唯一，比插入复杂得多
98. 验证二叉搜索树	中等	不修改树，改为向下传递取值区间来判定整棵树是否满足有序性质
235. 二叉搜索树的最近公共祖先	中等	同样靠比较大小决定下行方向，但终止条件是两个目标分居两侧
669. 修剪二叉搜索树	中等	按区间裁剪并重连子树，必须用递归返回值改写父指针，无法只走一条路径
108. 将有序数组转换为二叉搜索树	简单	反向构造：从有序序列自顶向下建树，还额外要求结果平衡