669 修剪二叉搜索树（递归修改）

心已赠人 2022-09-02 11:36 314阅读 0赞

**1. 问题描述：**

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, high\]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

**示例 1：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

输入：root = \[1,0,2\], low = 1, high = 2  
输出：\[1,null,2\]

**示例 2：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 1][]

输入：root = \[3,0,4,null,2,null,null,1\], low = 1, high = 3  
输出：\[3,2,null,1\]

**示例 3：**

输入：root = \[1\], low = 1, high = 2  
输出：\[1\]

**示例 4：**

输入：root = \[1,null,2\], low = 1, high = 3  
输出：\[1,null,2\]

**示例 5：**

输入：root = \[1,null,2\], low = 2, high = 4  
输出：\[2\]

**提示：**

树中节点数在范围 \[1, 10 ^ 4\] 内  
0 <= Node.val <= 10 ^ 4  
树中每个节点的值都是唯一的  
题目数据保证输入是一棵有效的二叉搜索树  
0 <= low <= high <= 10 ^ 4  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree

**2. 思路分析：**

分析题目可以知道在我们在遍历二叉搜索树的时候**递归**删除节点即可，也即在递归的时候修改当前根节点的左孩子或者是右孩子，因为是二叉搜索树所以我们可以根据当前根节点的值与low和high的大小关系决定递归哪一边的子树，若根节点的值小于low说明根节点左子树肯定不满足要求所以返回递归右子树的结果即可，若根节点的值大于high说明根节点的右子树肯定不满足要求所以返回递归左子树的结果即可，否则当前根节点的值位于区间内那么递归左右子树最终返回根节点即可。

**3. 代码如下：**

# class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        # 模拟即可
        def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
            if not root: return None
            # 左子树不满足要求那么返回递归右子树的结果, 相当于是删掉了左子树了因为下面在递归的时候修改了左右孩子, 而当前的节点一定是某个根节点的孩子所以最终是删除了当前根节点对应的所有子树
            if root.val < low: return self.trimBST(root.right, low, high)
            # 右子树不满足要求返回递归左子树的结果
            if root.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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/f3029c97fe51416c8d3468518aac407e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70 1]: /images/20220829/ba60933dd7ff49af8ab7453e1b7a3b08.png