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

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

  • 标签:树
  • 难度:中等

题目大意 #

给定一个二叉搜索树,和一个值 val。将 val 插入到二叉搜索树中,返回新的二叉搜索树的根节点。

解题思路 #

搜索二叉树的性质:

  • 左子树上任意节点值均小于根节点,即 root.left.val < root.val
  • 右子树上任意节点值均大于根节点,即 root.left.val > root.val

那么根据 val 和根节点的关系,则可以确定将 val 插入到哪个子树上。

如果插入的子树为空,则新建节点,赋值为 val。链接到该子树的父节点上。

如果插入的子树不为空,则根据 val 值和子树节点的大小关系,继续向下判断插入的子树位置。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)

        curr = root
        while curr:
            if val < curr.val:
                if not curr.left:
                    curr.left = TreeNode(val)
                    break
                else:
                    curr = curr.left
            else:
                if not curr.right:
                    curr.right = TreeNode(val)
                    break
                else:
                    curr = curr.right
        return root
本站总访问量  次  |  您是本站第  位访问者