二叉搜索树中的插入操作(面试常见题)

﹏ヽ暗。殇╰゛Y 2022-10-23 08:24 159阅读 0赞

# 一、题目描述 #

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

**示例1**：

![2e8e5672f28271fef576613291dab22d.png][]

输入：root = [4,2,7,1,3], val = 5
    输出：[4,2,7,1,3,5]
    解释：另一个满足题目要求可以通过的树是：

![42d836eec306a0460af3764b17bc64ae.png][]

**示例2：**

输入：root = [40,20,60,10,30,50,70], val = 25
    输出：[40,20,60,10,30,50,70,null,null,25]

**示例3：**

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
    输出：[4,2,7,1,3,5]

**提示：**

*  给定的树上的节点数介于 0 和 10^4 之间
 *  每个节点都有一个唯一整数值，取值范围从 0 到 10^8
 *  \-10^8 <= val <= 10^8
 *  新值和原始二叉搜索树中的任意节点值都不同

# 二、思路分析 #

二叉搜索树的数据域是有序的：

*  二叉搜索树左子树上所有结点的数据域都小于等于根结点的数据域
 *  二叉搜索树右子树上所有结点的数据域都大于等于根结点的数据域
 *  **左孩子 <= 根结点 <= 右孩子**
 *  利用二叉搜索树数据域的有序性可以快速定位节点

二叉搜索树的查找路线是一个非常明确的路径：  
我们会根据当前结点值的大小，决定路线应该是向左走还是向右走。  
val<当前节点值：往左走；val>当前节点值：往右走  
如果最后走到了一个空结点处，那就意味着这是我们需要插入节点的位置

如例1中的插入5：  
![58f04aaf9efd43574b148a11a3d4aa95.png][]

# 三、AC 代码 #

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} val
     * @return {TreeNode}
     */
    var insertIntoBST = function(root, val) {
         // 若 root 为空，说明当前是一个可以插入的空位
        if(!root) { 
            // 在此处插入值为val的节点
            root = new TreeNode(val)
            return root
        }
        
        if(root.val > val) {
            // 当前结点数据大于val，向左查找
            root.left = insertIntoBST(root.left, val)
        } else {
            // 当前结点数据小于val，向右查找
            root.right = insertIntoBST(root.right, val)
        }
    
        // 返回插入后二叉搜索树的根结点
        return root 
    };

# 四、总结 #

*  二叉搜索树左子树上所有结点的数据域都小于等于根结点的数据域
 *  二叉搜索树右子树上所有结点的数据域都大于等于根结点的数据域
 *  左孩子 <= 根结点 <= 右孩子
 *  利用二叉搜索树数据域的有序性可以快速定位节点

[文章链接：https://juejin.cn/post/6937626687802703902][https_juejin.cn_post_6937626687802703902]

[2e8e5672f28271fef576613291dab22d.png]: /images/20221023/7c0d4935fc2748f68613103b37b894b4.png
[42d836eec306a0460af3764b17bc64ae.png]: /images/20221023/4d8ee3c20ef04e4a98603293d030cf3a.png
[58f04aaf9efd43574b148a11a3d4aa95.png]: /images/20221023/c241c41505114f36b349a1ede836bf11.png
[https_juejin.cn_post_6937626687802703902]: https://juejin.cn/post/6937626687802703902