跳至主要內容

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

ITCharge大约 2 分钟

0701. 二叉搜索树中的插入操作open in new window

  • 标签:树、二叉搜索树、二叉树
  • 难度:中等

题目链接

题目大意

描述:给定一个二叉搜索树的根节点和要插入树中的值 val

要求:将 val 插入到二叉搜索树中,返回新的二叉搜索树的根节点。

说明

  • 树中的节点数将在 [0,104][0, 10^4] 的范围内。
  • 108Node.val108-10^8 \le Node.val \le 10^8
  • 所有值 Node.val 是独一无二的。
  • 108val108-10^8 \le val \le 10^8
  • 保证 valval 在原始 BST 中不存在。

示例

  • 示例 1:
输入: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]

解题思路

思路 1:递归

已知搜索二叉树的性质:

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

那么根据 val 和当前节点的大小关系,则可以确定将 val 插入到当前节点的哪个子树上。具体步骤如下:

  1. 从根节点 root 开始向下递归遍历。根据 val 值和当前子树节点 cur 的大小关系:
    1. 如果 val < cur.val,则应在当前节点的左子树继续遍历判断。
      1. 如果左子树为空,则新建节点,赋值为 val。链接到该子树的父节点上。并停止遍历。
      2. 如果左子树不为空,则继续向左子树移动。
    2. 如果 val >= cur.val,则应在当前节点的右子树继续遍历判断。
      1. 如果右子树为空,则新建节点,赋值为 val。链接到该子树的父节点上。并停止遍历。
      2. 如果右子树不为空,则继续向左子树移动。
  2. 遍历完返回根节点 root

思路 1:代码

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)

        cur = root
        while cur:
            if val < cur.val:
                if not cur.left:
                    cur.left = TreeNode(val)
                    break
                else:
                    cur = cur.left
            else:
                if not cur.right:
                    cur.right = TreeNode(val)
                    break
                else:
                    cur = cur.right
        return root

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)。其中 nn 是二叉搜索树的节点数。
  • 空间复杂度O(n)O(n)