（js）leetcode 701. 二叉搜索树中的插入操作

雨点打透心脏的1/2处 2023-01-05 05:28 159阅读 0赞

### 题目： ###

> 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
> 
> 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
> 
> 示例 1：
> 
> ![be940ab2e07119dcd45e5d58370fc5de.png][]  
> 输入：root = \[4,2,7,1,3\], val = 5  
> 输出：\[4,2,7,1,3,5\]  
> 解释：另一个满足题目要求可以通过的树是：
> 
> ![343ecc534e20d94866d953b0d107f198.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  
> 新值和原始二叉搜索树中的任意节点值都不同

### 思路： ###

> 1. 若root为空，直接创建一个新节点
> 
> 2. 一直往下找，知道找到叶子节点

### 代码实现： ###

/**
     * 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) {
        // 找到空位置插入新节点
        if(root == null) return new TreeNode(val);
        if(root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        if(root.val > val) {
            root.left = insertIntoBST(root.left, val)
        }
        return root;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[be940ab2e07119dcd45e5d58370fc5de.png]: /images/20221119/80568bdecb67424bbed2a90a24e3d8a4.png
[343ecc534e20d94866d953b0d107f198.png]: /images/20221119/b68cd74810cd431bb14668f8dac66f7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210111211348762.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl,size_16,color_FFFFFF,t_70