---
image: https://leetcode.com/static/images/LeetCode_Sharing.png
tags: leetcode
---
# Week2 Dragon [669. Trim a Binary Search Tree]

- 給一顆BST, 最低值low, 最高值high, 剪掉值對應的target
---
1. 利用postOrder, 先檢查左再右, 進入遞迴,
2. 最後判斷是否落在區間內, 若有則回傳root, 保持結構
3. 若無,則判斷:小於low回傳右節點,大於high回傳左節點
---

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        # 1. use postOrder, traverse leaf start from left node.
        # 2. check if 
        if root.left: root.left = self.trimBST(root.left, low, high)
        if root.right: root.right = self.trimBST(root.right, low, high)
        if root.val in range(low, high+1): return root
        elif root.val > high: return root.left
        elif root.val < low: return root.right

[669. Trim a Binary Search Tree]: https://leetcode.com/problems/trim-a-binary-search-tree/description/