专栏首页爱写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刷题】T154-二叉搜索树中的插入操作

    https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

    木又AI帮
  • LeetCode - 二叉搜索树中的插入操作

    原题地址:https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/

    晓痴
  • LeetCode 701 Insert into a Binary Search Tree

    因为是二叉搜索树,所以依次判断新值与每个节点的大小即可,大于当前节点,则判断此节点的右节点与新节点。小于当前节点,则判断此节点的左节点与新节点,直到子节点为空,...

    一份执着✘
  • Js算法与数据结构拾萃(4):二叉树

    因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转...

    一粒小麦
  • LeetCode通关:连刷三十九道二叉树,刷疯了!

    大家好,我是拿输出博客来督促自己刷题的老三,这一节我们来刷二叉树,二叉树相关题目在面试里非常高频,而且在力扣里数量很多,足足有几百道,不要慌,我们一步步来。我的...

    三分恶
  • LeetCode 701. 二叉搜索树中的插入操作(二叉查找树/插入)

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

    Michael阿明
  • Python3刷题系列(九)

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

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

    爱写bug
  • ​LeetCode刷题实战449:序列化和反序列化二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 纸上谈兵: AVL树

    作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 二叉搜索树的深度与搜索效率 我们在树, 二...

    Vamei
  • 48 Insert into a Binary Search Tree

    Given the root node of a binary search tree (BST) and a value to be inserted int...

    devi
  • 二叉树问题(三)-LeetCode 669、951、662、199、538、236(中序,层次遍历)

    给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果...

    算法工程师之路
  • 纸上谈兵: 树, 二叉树, 二叉搜索树

    树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

    Vamei
  • 【PAT甲级】Is It a Binary Search Tree

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • ​LeetCode刷题实战98:验证二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode - 二叉搜索树中的搜索

    原题地址:https://leetcode-cn.com/problems/search-in-a-binary-search-tree/

    晓痴
  • LintCode 在二叉查找树中插入节点题目分析

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

    desperate633
  • leetcode树之二叉搜索树的最近公共祖先

    这里采用递归的思路,并利用二叉搜索树的特性来解题;针对root.val大于p.val及q.val的递归执行lowestCommonAncestor(root.l...

    code4it
  • 二叉树-LeetCode 235、236、226、230(中序,LCA,DFS)

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 ...

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券