【LeetCode 刷题】二叉树-二叉搜索树的修改与构造

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为二叉搜索树的修改与构造相关的题目解析。

文章目录

• 701.二叉搜索树中的插入操作
• 450.删除二叉搜索树中的节点
• 669. 修剪二叉搜索树
• 108.将有序数组转换为二叉搜索树

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

题目链接

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

• 类似于二分查找，当 root 为空时，表明找到了插入位置，创建新的 TreeNode 返回

450.删除二叉搜索树中的节点

题目链接

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            ptr = root.right
            while ptr.left:
                ptr = ptr.left
            ptr.left = root.left
            root = root.right
        return root

• 要删除的节点可能会存在以下情况：
  • 左/右子树为空：直接返回另一侧的子树
  • 左/右子树都不空：需要修改树的结构，上述代码的逻辑为让 root.right 节点继位，需要将 root.left 节点代表的子树转移到刚好比 root 大的下一个位置（也即 root.right 子树中的最左侧节点）的左子树上
• ptr 即为找 root.right 中最左侧的节点的指针

669. 修剪二叉搜索树

题目链接

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val < low:
            return self.trimBST(root.right, low, high)
        elif root.val > high:
            return self.trimBST(root.left, low, high)
        else:
            root.left = self.trimBST(root.left, low, high)
            root.right = self.trimBST(root.right, low, high)
            return root

• 注意：例如当 root.val < low 时，不能直接返回 root.right，因为丢弃了左子树后，右子树还有可能因为节点值大于 high 而被修剪

108.将有序数组转换为二叉搜索树

题目链接

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        left = self.sortedArrayToBST(nums[:mid])
        right = self.sortedArrayToBST(nums[mid+1:])
        return TreeNode(nums[mid], left, right)