一、修剪二叉树（Leetcode 669）
递归法
class Solution:
def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
# 如果当前节点为空，直接返回空节点（递归终止条件）
if root is None:
return None
# 如果当前节点的值小于低值 low，说明当前节点及其左子树都不符合条件
# 所以应该修剪左子树，直接递归修剪右子树
if root.val < low:
return self.trimBST(root.right, low, high)
# 如果当前节点的值大于高值 high，说明当前节点及其右子树都不符合条件
# 所以应该修剪右子树，直接递归修剪左子树
if root.val > high:
return self.trimBST(root.left, low, high)
# 当前节点的值在 [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: TreeNode, L: int, R: int) -> TreeNode:
# 如果当前节点为空，直接返回 None（递归的终止条件）
if not root:
return None
# 处理头结点，确保 root 在区间 [L, R] 内
# 如果 root.val 小于 L，说明左子树所有的节点也小于 L，所以应该向右移动
# 如果 root.val 大于 R，说明右子树所有的节点也大于 R，所以应该向左移动
while root and (root.val < L or root.val > R):
if root.val < L:
root = root.right # 如果当前节点小于 L，跳到右子树
else:
root = root.left # 如果当前节点大于 R，跳到左子树
cur = root # 此时 root 应该已经在 [L, R] 范围内
# 处理左子树：确保所有左子树的节点值大于等于 L
while cur:
# 如果当前节点的左子树的节点值小于 L，应该删除这些节点
while cur.left and cur.left.val < L:
cur.left = cur.left.right # 将左子树的左子节点修剪掉，跳到下一个右子节点
cur = cur.left # 移动到左子树，继续修剪
cur = root # 重置 cur 为 root，继续处理右子树
# 处理右子树：确保所有右子树的节点值小于等于 R
while cur:
# 如果当前节点的右子树的节点值大于 R，应该删除这些节点
while cur.right and cur.right.val > R:
cur.right = cur.right.left # 将右子树的右子节点修剪掉，跳到下一个左子节点
cur = cur.right # 移动到右子树，继续修剪
# 返回修剪后的根节点
return root
二、将有序数组转换为二叉搜索树（Leetcode 108）
高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。本题关键就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
递归法：
class Solution:
def traversal(self, nums: List[int], left: int, right: int) -> TreeNode:
# 递归终止条件：如果左索引大于右索引，说明已经没有元素可以加入树中，返回 None
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
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
# 调用递归函数来构建树，初始的左右索引是从 0 到 len(nums) - 1
root = self.traversal(nums, 0, len(nums) - 1)
# 返回构建好的二叉搜索树
return root
迭代法：
from collections import deque
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if len(nums) == 0:
return None # 如果输入的数组为空，直接返回 None
root = TreeNode(0) # 初始根节点，值为 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) // 2 # 计算中间位置
curNode.val = nums[mid] # 将中间位置的元素赋值给当前节点
# 处理左子树
if left <= mid - 1:
curNode.left = TreeNode(0) # 创建左子树节点
nodeQue.append(curNode.left) # 将左子树节点入队
leftQue.append(left) # 左子树的区间
rightQue.append(mid - 1) # 左子树的右区间为 mid - 1
# 处理右子树
if right >= mid + 1:
curNode.right = TreeNode(0) # 创建右子树节点
nodeQue.append(curNode.right) # 将右子树节点入队
leftQue.append(mid + 1) # 右子树的左区间为 mid + 1
rightQue.append(right) # 右子树的右区间
return root # 返回最终的树根节点
三、把二叉搜索树转换为累加树（Leetcode 538）
本题类似数组从后向前累加，从树中可以看出累加的顺序是右中左，所以我们需要“反中序遍历”（右中左）这个二叉树，然后顺序累加
递归法：
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.pre = 0 # 记录前一个节点的值，初始为0
self.traversal(root) # 从根节点开始递归遍历
return root # 返回修改后的根节点
def traversal(self, cur):
if cur is None:
return # 如果当前节点为空，直接返回
self.traversal(cur.right) # 先递归右子树，因为我们需要从大到小访问节点
cur.val += self.pre # 将当前节点的值加上已遍历的节点值
self.pre = cur.val # 更新当前的前一个节点值
self.traversal(cur.left) # 再递归左子树
迭代法：
class Solution:
def __init__(self):
self.pre = 0 # 用于记录前一个节点的累加值，初始为0
def traversal(self, root):
stack = [] # 用来模拟递归过程的栈
cur = root # 当前节点初始化为根节点
# 栈不为空或者当前节点不为空时，继续遍历
while cur or stack:
if cur: # 如果当前节点不为空
stack.append(cur) # 将当前节点压入栈
cur = cur.right # 先处理右子树，因为我们需要逆序遍历
else:
cur = stack.pop() # 弹出栈顶元素（中序遍历的当前节点）
# 当前节点的值加上之前累加的值
cur.val += self.pre
self.pre = cur.val # 更新前一个节点的累加值
cur = cur.left # 转到左子树继续遍历
def convertBST(self, root):
self.pre = 0 # 重置累加值
self.traversal(root) # 开始遍历并转换树
return root # 返回转换后的根节点