leetCode日记–701.Insert into Binary Search tree

发布于 2020-09-30  105 次阅读


碎碎念:17级那点人都能保研40个人,我觉得我又有机会卷了。冲!但是LeetCode还是要好好刷,嗯。

题目如下:

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example, 

Given the tree:

    4
   / \
  2   7
 / \
1   3


And the value to insert: 5
You can return this binary search tree:

     4
   /   \
  2     7
 / \   /
1   3 5

思路:

这题真的很简单,就用二叉搜索树的定义就可以了。每次的值与当前节点的值比较,大则往右子树继续比较,小则进入左子树比较,直到找到新节点该在的叶子的位置上。

迭代实现:

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode newNode = new TreeNode(val);
        TreeNode cur = root;
        if(root==null)
            return newNode;
        while(cur!=null){
            if(val>cur.val){
                if(cur.right!=null){
                    cur=cur.right;
                    continue;
                }
                else{
                    cur.right=newNode;
                    break;
                }
            }
            if(val<cur.val){
                if(cur.left!=null){
                    cur=cur.left;
                    continue;
                }
                else{
                    cur.left=newNode;
                    break;
                }
            }
        }
        return root;
    }
}

递归实现:

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            TreeNode newNode = new TreeNode(val);
            root = newNode;
            return root;
        }
        if(val < root.val)
            root.left = insertIntoBST(root.left,val);
        if(val > root.val)
            root.right = insertIntoBST(root.right,val);
        return root;
    }
}

事实证明迭代在时间和空间上都比递归好一些。


你好哇!欢迎来到雷公马碎碎念的地方:)