# 669. Trim a Binary Search Tree

[https://leetcode.com/problems/trim-a-binary-search-tree/](https://leetcode.com/problems/trim-a-binary-search-tree/)

## solution

* 小于low，那么所有左子树都小于low可以舍弃，返回右子树
* 大于high，那么所有右子树都大于high可以舍弃，返回左子树
* 对于位于期间的节点，递归其子树，左子树的返回节点接在左子树上，可能是正常节点，也可能是舍弃后返回的节点

```python
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](1110.-delete-nodes-and-return-forest)
