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)
        if root.val>high:
            return self.trimBST(root.left,low,high)
        root.left=self.trimBST(root.left,low,high)
        root.right=self.trimBST(root.right,low,high)
        return root

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

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

538 把二叉搜索树转换为累加树

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def sub(root):
            nonlocal total
            if root:
                sub(root.right)
                total+=root.val
                root.val=total
                sub(root.left)
            return root
        total=0
        sub(root)
        return root