专栏首页爱写BugLeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

LeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

题目:

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

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.

例如,

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和 插入的值: 5

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

         4
       /   \
      2     7
     / \   /
    1   3 5

或者这个树也是有效的:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

解题思路:

二叉搜索树的插入操作与搜索操作类似,对于每个节点:

  1. 根据节点值与目标节点值的关系,搜索左子树或右子树;
  2. 如果目标值小于节点的值,则继续在左子树中搜索;
  3. 如果目标值大于节点的值,则继续在右子树中搜索。
  4. 重复步骤 1 直到到达外部节点;
  5. 根据节点的值与目标节点的值的关系,将新节点添加为其左侧或右侧的子节点。

递归法:

Java:

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

Python:

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        else:
            root.left = self.insertIntoBST(root.left, val)
        return root

Golang:

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        t := new(TreeNode)
        t.Val = val
        return t
    }
    if val > root.Val {
        root.Right = insertIntoBST(root.Right, val)
    } else {
        root.Left = insertIntoBST(root.Left, val)
    }
    return root
}

迭代法:

Java:

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

Python:

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        node = root
        while node:
            if val > node.val:
                if not node.right:
                    node.right = TreeNode(val)
                    return root
                else:
                    node = node.right
            else:
                if not node.left:
                    node.left = TreeNode(val)
                    return root
                else:
                    node = node.left
        return TreeNode(val)

Golang:

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    t := new(TreeNode)
    t.Val = val
    node := root
    for node != nil {
        if val > node.Val {
            if node.Right == nil {
                node.Right = t
                return root
            } else {
                node = node.Right
            }
        } else {
            if node.Left == nil {
                node.Left = t
                return root
            } else {
                node = node.Left
            }
        }
    }
    return t
}

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

    给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL。

    爱写bug
  • LeetcCode 27:移除元素 Remove Element

    给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

    爱写bug
  • LeetcCode 27:移除元素 Remove Element(python、java)

    给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

    爱写bug
  • LeetCode 235 Lowest Common Ancestor of a Binary Search Tree

    题解:递归的时候判断如果两个节点的值在父节点两边,那个这个父节点就是最近的公共父节点。否则按照二叉搜索树的规则递归下去。

    ShenduCC
  • LintCode 验证二叉查找树题目分析代码

    2 / 1 4 / 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

    desperate633
  • 【leetcode刷题】T131-二叉搜索树的最近公共祖先

    https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

    木又AI帮
  • LintCode 在二叉查找树中插入节点题目分析

    给定一棵二叉查找树和一个新的树节点,将节点插入到树中。 你需要保证该树仍然是一棵二叉查找树。

    desperate633
  • 85. 在二叉查找树中插入节点常规操作

    You can assume there is no duplicate values in this tree + node.

    和蔼的zhxing
  • 【LeetCode 235.二叉搜索树的最近公共祖先】JavaScript/C++实现

    例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

    心谭博客
  • PHP生成推广海报的方法

    经常有这样的需求,就是需要在生成推广海报,包含指定的二维码,分享出去别人扫码之后就可以确定用户推荐关系。

    猿哥

扫码关注云+社区

领取腾讯云代金券