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

link

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

思路

题目中说随便返回一种结果即可，所以可以一条路走到底，不用遍历整个树

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        cur = root
        node = TreeNode(val)
        pre = None
        if root == None:
            return node
        while cur:
            pre = cur
            if cur.val > val:
                cur = cur.left
            else:
                cur = cur.right

        if pre.val < val:
            pre.right = node

        else:
            pre.left = node
            
        return root

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

link

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

思路

找到节点后，需要修改以当前节点为根节点的子树，判断其左右节点是否存在，可以按照如下修改：

把左子树作为当前根节点，右子树放到原有左子树的最右边
右子树作为当前根节点，左子树放到原有左子树的左边

返回的值为更新后的子树

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return None
            if node.val > key:
                node.left =  dfs(node.left)
                return node
            
            if node.val < key:
                node.right = dfs(node.right)
                return node
            
            if not node.left and not node.right:
                return None
            if not node.left and node.right:
                return node.right
            if node.left and not node.right:
                return node.left
            
            cur = node.right
            pre = node
            while cur:
                pre = cur
                cur = cur.left
            pre.left = node.left

            return node.right

        return dfs(root)

669. 修剪二叉搜索树

link

给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。

思路

直接的思路是判断当前节点是否在区间外，如果在区间左边就直接删除左子树，在区间右边就删除右子树。但是，子树里面可能有在区间内的节点，如图所示

使用递归的方法，在遇到上述两种情况时，可以直接返回递归子树的结果。接下来就处理根节点在区间内的情况，即根节点的左右子树分别递归处理，并将返回结果赋值给左右指针。

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        
        def dfs(node, l, h):
            if not node:
                return None
            if node.val > h:
                return dfs(node.left, l, h)
            if node.val < l:
                return dfs(node.right, l, h)
            
            # 当前节点在区间内
            node.left = dfs(node.left, l, h)
            node.right = dfs(node.right, l, h)
            return node
        
        return dfs(root, low, high)

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

link

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

思路

递归调用：

递归函数接受当前的区间，返回基于当前区间构建的子树
当区间长度为 0 时就停止递归，返回空
主要逻辑：
- 找到区间中点，基于区间中点创建根节点
- 划分区间，左区间构建左子树，右区间构建右子树
- 将两个子树赋值给根节点

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        
        def dfs(num):
            if len(num) == 0:
                return None
            index = len(num) // 2
            root = TreeNode(num[index])

            root.left = dfs(num[:index])
            root.right = dfs(num[index+1:])

            return root
        return dfs(nums)