代码随想录算法训练营第二十三天|第六章二叉树：669. 修剪二叉搜索树，108.将有序数组转换为二叉搜索树，538.把二叉搜索树转换为累加树（python）

669. 修剪二叉搜索树

视频讲解链接

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

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

视频讲解链接

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        root = self.traversal(nums, 0, len(nums)-1)
        return root
 
    def traversal(self, nums, left, right):
        if left > right: #区间不合法
            return None
        
        mid = left + (right - left) // 2 #找中点
        mid_root = TreeNode(nums[mid])
        mid_root.left = self.traversal(nums, left, mid-1)
        mid_root.right = self.traversal(nums, mid+1, right)
        return mid_root

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

 视频讲解链接

class Solution:
    def __init__(self):
        self.pre = TreeNode()
 
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.traversal(root)
        return root
 
    def traversal(self, root: TreeNode) -> None:
        if not root: 
            return None
        self.traversal(root.right)  # 右
        root.val += self.pre.val    # 中
        self.pre = root             
        self.traversal(root.left)   # 左