二叉树 | 二叉搜索树的插入操作 | leecode刷题笔记

发布于:2023-01-20 ⋅ 阅读:(16) ⋅ 点赞:(0) ⋅ 评论:(0)

跟随carl代码随想录刷题
语言:python


701. 二叉搜索树中的插入操作

题目:给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
在这里插入图片描述
输入:root = [4,2,7,1,3], val = 5
输出:[4,2,7,1,3,5]
解释:另一个满足题目要求可以通过的树是:
在这里插入图片描述
示例 2:
输入:root = [40,20,60,10,30,50,70], val = 25
输出:[40,20,60,10,30,50,70,null,null,25]
示例 3:
输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出:[4,2,7,1,3,5]

题目分析

本题不涉及调整二叉树的结构。
只要遇到空节点,将值插入进去即可。
⭐️二叉搜索树不用遍历整棵树,否则是对二叉搜索树的侮辱😆

完整代码如下

递归法——有返回值

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:

        
        if not root:
            return TreeNode(val)  # 如果数为空,那val就作为根节点
        
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
            # root = root.left
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)
            # root = root.right
        return root

递归法——一种更简便的方式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:    
        newNode = TreeNode(val)
        if not root:
            return newNode  # 如果数为空,那val就作为根节点
        
        if not root.left and val < root.val:
            root.left = newNode
        if not root.right and val > root.val:
            root.right = newNode
        
        if val < root.val:
            self.insertIntoBST(root.left, val)
        if val > root.val:
            self.insertIntoBST(root.right, val)
        
        return root

迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:    
        if not root:
            return TreeNode(val)  # 如果数为空,那val就作为根节点
        
        parent = None
        cur = root
        
        while cur:
            if cur.val > val:
                parent = cur
                cur = cur.left
            elif cur.val < val:
                parent = cur
                cur = cur.right
        if parent.val > val:
            parent.left = TreeNode(val)
        else:
            parent.right = TreeNode(val)
        
        return root

网站公告

欢迎关注微信公众号

今日签到

点亮在社区的每一天
签到