修剪二叉搜索树

669. 修剪二叉搜索树

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

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

如果访问节点的值在[low,high]之间，那么就递归访问左右子树。
如果节点值小于low，那么就去访问右子树，因为左子树的值一定更小。（返回右子树的根节点，并且右子树也要进行修剪）
如果节点值大于high，那么就去访问左子树，因为右子树的值一定更大。（返回左子树的根节点，并且左子树也要进行修剪）

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

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

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

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

有点类似二分法，每次取中间值作为根节点，然后递归构造左右子树。（左闭右闭）

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

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

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

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