有点像是删除二叉搜索树的变形，改变了删除条件而已。
递归法：

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return rootif root.val < low:      # 当前节点小于low，不用再看其左子树，遍历其右子树即可right = self.trimBST(root.right, low, high)return rightif root.val > high:     # 当前节点大于high，不用再看其右子树，遍历其左子树即可left = self.trimBST(root.left, low, high)return leftroot.left = self.trimBST(root.left, low, high)      # root.left接入符合条件的左孩子root.right = self.trimBST(root.right, low, high)    # root.right接入符合条件的右孩子return root

迭代法：

'''
在剪枝的时候，可以分为三步：
将root移动到[L, R] 范围内，注意是左闭右闭区间
剪枝左子树
剪枝右子树
'''
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return root# 处理头节点，把头结点放到[low, high]范围内while root and (root.val < low or root.val > high):if root.val < low:      # 小于low往右走root = root.rightelse:                   # 大于high往左走root = root.leftcurleft, curright = root, root# 处理左孩子元素小于low的情况while curleft:while curleft.left and curleft.left.val < low:curleft.left = curleft.left.rightcurleft = curleft.left# 处理右孩子元素大于high的情况while curright:while curright.right and curright.right.val > high:curright.right = curright.right.leftcurright = curright.rightreturn root

对于奇数长度的数组可以直接取中点，对于偶数长度的数组则需要用mid = int(left + ((right - left) / 2))。
中点作为根节点，左右两侧则分别为左子树和右子树，依次进行递归遍历。

class Solution:# 左闭右闭区间[left, right]def traversal(self, nums, left, right):if left > right:return Nonemid = int(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 rootdef sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:root = self.traversal(nums, 0, len(nums) - 1)return root

迭代法：用队列模拟递归过程

from collections import dequeclass Solution:def sortedArrayToBST(self, nums: List[int]) -> TreeNode:if len(nums) == 0:return Noneroot = TreeNode(0)  # 初始根节点nodeQue = deque()   # 放遍历的节点leftQue = deque()   # 保存左区间下标rightQue = deque()  # 保存右区间下标nodeQue.append(root)               # 根节点入队列leftQue.append(0)                  # 0为左区间下标初始位置rightQue.append(len(nums) - 1)     # len(nums) - 1为右区间下标初始位置while nodeQue:curNode = nodeQue.popleft()left = leftQue.popleft()right = rightQue.popleft()mid = left + (right - left) // 2curNode.val = nums[mid]     # 将mid对应的元素给中间节点if left <= mid - 1:         # 处理左区间curNode.left = TreeNode(0)nodeQue.append(curNode.left)leftQue.append(left)rightQue.append(mid - 1)if right >= mid + 1:        # 处理右区间curNode.right = TreeNode(0)nodeQue.append(curNode.right)leftQue.append(mid + 1)rightQue.append(right)return root

题目中的累加是右中左的顺序进行累加，从最大的节点值累加到最小的节点值。
所以要反中序遍历该二叉树，然后顺序累加。
需要一个pre指针记录当前节点的前一个节点，这样才能方便累加。

class Solution:def traversal(self, cur):       # 右中左遍历if not cur:                 # 终止条件returnself.traversal(cur.right)   # 右cur.val += self.pre         # 中self.pre = cur.valself.traversal(cur.left)    # 左def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.pre = 0                # 记录前一个节点的数值self.traversal(root)return root

或者写成这样也可以：

class Solution:def __init__(self):               # 记录前一个节点的数值self.pre = 0def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:                  # 终止条件returnself.convertBST(root.right)   # 右root.val += self.pre          # 中self.pre = root.valself.convertBST(root.left)    # 左return root

迭代法：

class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: return rootstack = []result = []cur = rootpre = 0         # 记录前一个节点的数值while cur or stack:if cur:                 # 右stack.append(cur)cur = cur.rightelse: cur = stack.pop()   # 中cur.val+= prepre = cur.valcur =cur.left       # 左return root