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
Last updated