代码随想训练营第二十三天（Python）｜ 669. 修剪二叉搜索树 、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树
树的修剪方式赋值。
1、递归法

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root is None:
            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

2、迭代法

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root is None:
            return None
        # 先找到 root 的位置在 [low, high] 区间
        while root and (root.val < low or root.val > high):
            if root.val < low:
                root = root.right
            else:
                root = root.left

        cur = root
        # 处理小于 low 的部分
        while cur:
            while cur.left and cur.left.val < low:
                cur.left = cur.left.right # 赋值剪枝
            cur = cur.left

        cur = root
        while cur:
            while cur.right and cur.right.val > high:
                cur.right = cur.right.left # 赋值剪枝
            cur = cur.right

        return root

108.将有序数组转换为二叉搜索树
1、递归法

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.traversal(nums, 0, len(nums) - 1)

    def traversal(self, nums, left, right):
        if left > right:
            return None
        mid = left + (right - left) // 2
        root = TreeNode(nums[mid])
        root.left = self.traversal(nums, left, mid-1)
        root.right = self.traversal(nums, mid+1, right)
        return root

538.把二叉搜索树转换为累加树
1、迭代法

    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return
        cur = root
        stack = []
        pre = 0 # 记录上一个节点的值
        while cur or stack:
            # 右
            if cur:
                stack.append(cur)
                cur = cur.right
            else:
                # 中
                cur = stack.pop()
                if pre:
                    cur.val += pre.val
                pre = cur
                # 左
                cur = cur.left
        return root

2、递归

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.pre = 0 # 记录前一个节点
        self.traversal(root)
        return root

    def traversal(self, root):
        if root is None:
            return 
        self.traversal(root.right) # 右
        # 中
        if self.pre:
            root.val += self.pre
        self.pre = root.val
        self.traversal(root.left) # 左