1
class Solution:
2
    # 利用 BST 的性质剪枝，递归判断当前节点是否保留，并修剪左右子树
3
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
4
        if not root:
5
            return None
6
        if root.val < low:
7
            # 当前节点值小于区间下限，只保留右子树
8
            return self.trimBST(root.right, low, high)
9
        if root.val > high:
10
            # 当前节点值大于区间上限，只保留左子树
11
            return self.trimBST(root.left, low, high)
12
        # 当前节点在区间范围内，递归修剪左右子树
13
        root.left = self.trimBST(root.left, low, high)
14
        root.right = self.trimBST(root.right, low, high)
15
        return root

1
class Solution:
2
    # 分治 - 取中间元素作为根节点，左右子数组递归构造左右子树
3
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
4
        return self.build(nums, 0, len(nums) - 1)
5

6
    def build(self, nums: List[int], left: int, right: int) -> Optional[TreeNode]:
7
        if left > right:
8
            return None
9
        # 取中间位置作为根，避免溢出写法
10
        mid = left + (right - left) // 2
11
        node = TreeNode(nums[mid])
12
        # 递归构建左右子树
13
        node.left = self.build(nums, left, mid - 1)
14
        node.right = self.build(nums, mid + 1, right)
15
        return node

1
class Solution:
2
    # 反中序遍历（右 -> 根 -> 左），累加和
3
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
4
        self.prev = 0  # 累加和
5
        return self.traverse(root)
6

7
    def traverse(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
8
        if not root:
9
            return None
10
        self.traverse(root.right)       # 遍历右子树
11
        self.prev += root.val           # 更新累加值
12
        root.val = self.prev            # 当前节点值替换为累加和
13
        self.traverse(root.left)        # 遍历左子树
14
        return root