文章目录LeetCode669. 修剪二叉搜索树思路解答LeetCode108. 将有序数组转换为二叉搜索树思路解答LeetCode538. 把二叉搜索树转换为累加树思路解答LeetCode669. 修剪二叉搜索树https://leetcode.cn/problems/trim-a-binary-search-tree/思路递归终止条件当前节点为空返回 None。curr.val low说明当前节点及其左子树都更小直接剪掉。但右子树中可能有符合条件的节点因此递归修剪右子树并将结果作为新的子树返回。curr.val high同理递归修剪左子树并返回。low curr.val hight保留当前节点分别递归修剪左子树和右子树将修剪后的结果赋值给当前节点的左右子节点然后返回当前节点。解答# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:deftrimBST(self,root:Optional[TreeNode],low:int,high:int)-Optional[TreeNode]:ifnotroot:returnNoneifroot.vallow:# 根节点较小左子树剪掉递归处理右子树returnself.trimBST(root.right,low,high)elifroot.valhigh:# 根节点较大右子树剪掉递归处理左子树returnself.trimBST(root.left,low,high)else:# 根节点在范围内修剪左右子树并重新连接root.leftself.trimBST(root.left,low,high)root.rightself.trimBST(root.right,low,high)returnrootLeetCode108. 将有序数组转换为二叉搜索树https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/思路利用数组已排序的特性通过二分法不断将数组分成左右两部分选择数组的中间元素作为当前子树的根节点。中间元素左边的子数组递归构建左子树。中间元素右边的子数组递归构建右子树。解答# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defsortedArrayToBST(self,nums:List[int])-Optional[TreeNode]:nlen(nums)ifn1:returnNonemidn//2nodeTreeNode()node.valnums[mid]left_numsnums[:mid]right_numsnums[mid1:]node.leftself.sortedArrayToBST(left_nums)node.rightself.sortedArrayToBST(right_nums)returnnodeLeetCode538. 把二叉搜索树转换为累加树https://leetcode.cn/problems/convert-bst-to-greater-tree/思路利用反向中序遍历右-中-左则每个访问节点都变成所有已访问过的节点总和。例如B S T BSTBST[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]有其反向中序遍历结果为[8, 7, 6, 5, 4, 3, 2, 1, 0]其更改后为[8, 15, 21, 26, 30, 33, 35, 36, 36]。解答# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution:defconvertBST(self,root:Optional[TreeNode])-Optional[TreeNode]:total0# 反向中序遍历stk[]currrootwhilestkorcurr:whilecurr:stk.append(curr)currcurr.right currstk.pop()totalcurr.val# 统计已访问过的节点总和curr.valtotal# 更新节点currcurr.left# 转到左子树returnroot