leetcode(17)二叉搜索树系列题目

669. 修剪二叉搜索树

注意：本题需要返回值，因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。

但是有返回值，更方便，可以通过递归函数的返回值来移除节点。

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return
        if root.val < low:
            return self.trimBST(root.right, low, high)  #直接返回右边的
        elif root.val > high:
            return self.trimBST(root.left, low, high)   #直接返回左边的
        elif low <= root.val <= high:
            root.left = self.trimBST(root.left, low, high)
            root.right = self.trimBST(root.right, low, high)
            return root

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

第3个自己写出来的递归树！

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

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

换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，从后向前，挨个累加即可。
从树中可以看出累加的顺序是右中左，所以反中序遍历这个二叉树，然后顺序累加就可以了。
递归函数不需要返回值做什么操作了，要遍历整棵树。

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