leetcode701-二叉搜索树中的插入操作

原题

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

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

例如, 

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和 插入的值: 5

你可以返回这个二叉搜索树:

         4
       /   \
      2     7
     / \   /
    1   3 5

或者这个树也是有效的:

         5
       /   \
      2     7
     / \
    1   3
         \
          4

解法

思想

与搜索操作类似,对于每个节点,我们将:

  1. 根据节点值与目标节点值的关系,搜索左子树或右子树;
  2. 重复步骤 1 直到到达外部节点;
  3. 根据节点的值与目标节点的值的关系,将新节点添加为其左侧或右侧的子节点。

如此递归。

代码

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode701-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e4%b8%ad%e7%9a%84%e6%8f%92%e5%85%a5%e6%93%8d%e4%bd%9c/

发表评论

电子邮件地址不会被公开。