day18-数据结构力扣

669. 修剪二叉搜索树

思路

利用二叉搜索树左小右大的特性递归处理

若当前节点值小于下界 `low`，则该节点及其左子树均不在区间内，只需递归修剪并返回其右子树

若当前节点值大于上界 `high`，则该节点及其右子树均不在区间内，只需递归修剪并返回其左子树

若节点值在 `[low, high]` 范围内，则保留该节点

同时递归修剪其左右子树并重新连接，最终得到修剪后的合法二叉搜索树。

提交

class Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]: if not root: return root # 当前节点值 < 下界，整棵左子树都无效，只保留并修剪右子树 if root.val < low: right = self.trimBST(root.right, low, high) return right # 当前节点值 > 上界，整棵右子树都无效，只保留并修剪左子树 if root.val > high: left = self.trimBST(root.left, low, high) return left # 当前节点在范围内，正常修剪左右子树并连接 root.left = self.trimBST(root.left, low, high) root.right = self.trimBST(root.right, low, high) return root

• 节点 < 下界

• 左子树所有节点都比它更小 →直接丢掉整个左子树只保留右子树，继续修剪右子树并返回

• 节点 > 上界

• 右子树所有节点都比它更大 →直接丢掉整个右子树只保留左子树，继续修剪左子树并返回

思路

我刚开始是想找到根节点，然后左右两边依次排，但是我代码写出来通过23/31

怎么说，还是提升了一点，能写递归能通过20多个用例，最开始啥都不会。

看一下题解

原来先找到根节点的思路没有问题，是因为我递归又加了for循环才超时的

好像这里for循环很多余，直接删掉，再加上递归的结束条件就可以提交了

提交

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: # 递归终止条件：数组为空，返回空 if not nums: return None # 取中间位置作为根节点（高度平衡BST核心） mid = (len(nums) - 1) // 2 root = TreeNode(nums[mid]) # 左半数组 → 左子树 root.left = self.sortedArrayToBST(nums[:mid]) # 右半数组 → 右子树 root.right = self.sortedArrayToBST(nums[mid+1:]) return root

思路

刚开始没想到

规则：每个节点的值 = 原树中 ≥ 它的所有节点之和

正确做法：

• 反序中序遍历：右 → 根 → 左（从大到小遍历）

• 用一个变量累加和，边遍历边更新节点值

他这里有一个技巧就是反序中序遍历，那为什么会想到这个，因为正序的不好做。或者说更麻烦一点

我之前的思路是把中序遍历，得到数组，然后得到mid，每次算nums[mid:]求和。

提交

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]: self.total = 0 # 记录累加和 self.dfs(root) return root # 反序中序遍历：右 → 根 → 左 def dfs(self, root): if not root: return # 先遍历右子树（更大的数） self.dfs(root.right) # 更新当前节点值 self.total += root.val root.val = self.total # 再遍历左子树（更小的数） self.dfs(root.left)

然后二叉树的题就结束了？对，但其实还掌握的不够扎实，但是慢慢来吧。