669. 修剪二叉搜索树

递归

一道easy题目，但是直接上手有点难度，麻烦的地方在于会改变二叉树的结构 注意这是一颗二叉搜索树，应该能利用到二叉搜索树的性质来遍历 然后给定区间是$[low,high]$ 一颗二叉搜索树的定义是左小右大的，那么一共还是三种情况，设根节点的值是val 则

low<=val<=high 无事发生，但是要继续判断左右子树，删除掉值域外的结点val<low 根节点都小于low了，根据二叉搜索树的性质来看，此时根节点的左子树所有value都会小于low，无需递归左子树，但是可能右子树会大于low，所以要递归判断右子树val>high 根节点的值大于high，是val<low的镜像情况，无需递归右子树，但是左子树仍然可能存在符合的结点

根据上述三种情况，我们假设trimBST能够根据low和high的范围来修建一个二叉搜索树，并且返回修剪后的结点 然后依次设计trimBST里面的三个操作

边界情况 root为空的时候我们直接返回root就行 还有一个特殊情况，就是这个根节点无左右孩子，但是它当前的值不属于$[low,high]$这个区间，那么我们也是直接返回None，表示删除了这个节点一般情况（当前层次需要执行的操作） 其实就是我们上面分析的三种情况，唯一麻烦的地方，就是我们要更新根节点，但是更新根节点的情况只会在2、3这两种情况下发生，发生的时候必有一颗子树被舍弃，我们直接将另一个孩子结点作为新的根节点返回即可返回 依然是根据三种情况来返回 1 返回root，其左右子树更新为trimBST(root.left,…)，trimBST(root.right,…) 2 返回trimBST(root.right,…) 3 返回trimBST(root.left,…)

写出伪代码

def trimBST(root,low,high): if 根节点为空: return None if 根节点左右子树为空，并且根节点的值不属于[low,high] return None if low<=root.val<=high: root.left = trimBST(root.left,low,high) root.right = trimBST(root.right,low,high) return root elif root.val<low: return trimBST(root.right,low,high) elif root.val>high: return trimBST(root.left,low,high)

通过了 递归就是这么神奇，只需要考虑 1 边界条件——特殊情况 2 当前操作——一般情况 3 返回值 这三个情况，题目迎刃而解

上述代码的if逻辑有些混乱，更改后更加简洁，无左右孩子子树的情况不需要额外放出来

class Solution: def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode: # 边界情况 if not root: return root val = root.val if val<low: return self.trimBST(root.right,low,high) elif val>high: return self.trimBST(root.left,low,high) root.left = self.trimBST(root.left,low,high) root.right = self.trimBST(root.right,low,high) return root