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

深藏阁楼爱情的钟 2023-02-20 06:38 89阅读 0赞

#### 题目描述 ####

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

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

例如,

给定二叉搜索树:

4
       / \
      2   7
     / \
    1   3

和 插入的值: 5  
你可以返回这个二叉搜索树:

4
       /   \
      2     7
     / \   /
    1   3 5

或者这个树也是有效的:

5
       /   \
      2     7
     / \   
    1   3
         \
          4

#### 解题思路 ####

使用递归的迭代的方法实现。

#### 代码实现 ####

**递归实现：**

**迭代实现：**

/** * 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){ 
            return new TreeNode(val)
        }
        let cur = root
        while(cur){ 
            if(val > cur.val){ 
               if(!cur.right){ 
                    cur.right = new TreeNode(val)
                    return root
               }else{ 
                   cur = cur.right
               }
            }else{ 
                if(!cur.left){ 
                    cur.left = new TreeNode(val)
                    return root
                }else{ 
                    cur = cur.left
                }
            }
        }
        return root
    };

#### 提交结果 ####

**递归实现：**  
![在这里插入图片描述][20200624003808814.png]  
**迭代实现：**  
![在这里插入图片描述][20200624004754889.png]

[20200624003808814.png]: https://img-blog.csdnimg.cn/20200624003808814.png
[20200624004754889.png]: https://img-blog.csdnimg.cn/20200624004754889.png