代码随想录 -- 二叉树 -- 修剪二叉搜索树

 669. 修剪二叉搜索树 - 力扣（LeetCode）

思路：

递归出口：

• 当root为空时，返回空。
• 当root的值比low小时，如果root没有右子树，直接返回空；否则返回trimBST(root.right,low,high)。
• 当root的值比high大时，如果root没有左子树，直接返回空；否则返回trimBST(root.left,low,high)。

单层递归逻辑：

当root的值在low和high中间时，令root的左孩子为trimBST(root.left,low,high)；令root的右孩子为trimBST(root.right,low,high)。

最后返回root。

class Solution(object):
    def trimBST(self, root, low, high):
        if root==None:
            return None
        elif root.val<low:
            if root.right==None:
                return None
            else:
                return self.trimBST(root.right,low,high)
        elif root.val>high:
            if root.left==None:
                return None
            else:
                return self.trimBST(root.left,low,high)
        else:
            root.left=self.trimBST(root.left,low,high)
            root.right=self.trimBST(root.right,low,high)
        return root