669. Trim a Binary Search Tree

https://leetcode.com/problems/trim-a-binary-search-tree/

solution

• 小于low，那么所有左子树都小于low可以舍弃，返回右子树

• 大于high，那么所有右子树都大于high可以舍弃，返回左子树

• 对于位于期间的节点，递归其子树，左子树的返回节点接在左子树上，可能是正常节点，也可能是舍弃后返回的节点

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val > high:
            return self.trimBST(root.left, low, high)
        if root.val < low:
            return self.trimBST(root.right, low, high)

        if root.val >= low and root.val <= high:
            root.left = self.trimBST(root.left, low, high)
            root.right = self.trimBST(root.right, low, high)
        return root

时间复杂度：O() 空间复杂度：O()

follow up

1110. Delete Nodes And Return Forest