代码随想录算法训练营第22天 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树：https://leetcode.cn/problems/trim-a-binary-search-tree/description/
     代码随想录：
     https://programmercarl.com/0669.修剪二叉搜索树.html#算法公开课
     108.将有序数组转换为二叉搜索树
     https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
     代码随想录：
     https://programmercarl.com/0108.将有序数组转换为二叉搜索树.html#算法公开课
     538.把二叉搜索树转换为累加树
     https://leetcode.cn/problems/convert-bst-to-greater-tree/
     代码随想录：
     https://programmercarl.com/0538.把二叉搜索树转换为累加树.html

669. 修剪二叉搜索树

题解思路

• 递归法：判断当前节点是否符合要求；删除当下节点；
• 迭代法：（不需要用栈遍历）
  1. 将root移动至区间内
  2. 修剪左子树
  3. 修剪右子树

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

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

        curr = root
        while curr:
            while curr.right and curr.right.val>high:
                curr.right = curr.right.left
            curr = curr.right
        return root

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

题解思路

• 平衡二叉树：从中间节点开始划分数组；
• 递归法：每次选取中间节点、递归模拟赋值即可；
• 迭代法：3个队列模拟选取节点和赋值的过程；

题解代码

递归法

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

迭代法

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums)==0:
            return None
        root = TreeNode(0)
        node_que = collections.deque([root])
        left_que = collections.deque([0])
        right_que = collections.deque([len(nums)-1])

        while node_que:
            curr_node = node_que.popleft()
            left = left_que.popleft()
            right =right_que.popleft()
            mid = left+(right-left)//2
            curr_node.val = nums[mid]

            if left<=mid-1:
                curr_node.left = TreeNode(0)
                node_que.append(curr_node.left)
                left_que.append(left)
                right_que.append(mid-1)
            if right>=mid+1:
                curr_node.right = TreeNode(0)
                node_que.append(curr_node.right)
                left_que.append(mid+1)
                right_que.append(right)
        return root

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

题解思路

• 递归法：先计算每个右子树。每个值等于前一个值累加；
• 迭代法：
  • 采用栈 将所有右节点进入栈，依次遍历其左子树
  • 记录self.pre

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

class Solution:
    def __init__(self):
        self.pre = 0

    def trans(self,root):
        if not root:
            return None

        st = []
        curr = root
        while st or curr:
            if curr:
                st.append(curr)
                curr = curr.right
            else:
                curr = st.pop()
                curr.val = curr.val+self.pre
                self.pre = curr.val
                curr = curr.left

    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.trans(root)
        return root