[leetcode] 669. Trim a Binary Search Tree (python)

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

난이도 : Medium

 

풀이

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        
        def trim(node) -> Optional[TreeNode]:
            
            if node:
                if node.val > high:
                    return trim(node.left)
                elif node.val < low:
                    return trim(node.right)
                else:
                    node.left = trim(node.left)
                    node.right = trim(node.right)
                    return node

        return trim(root)

 

어려워보이지만 이진탐색트리(BST)이기 때문에 오히려 쉽게 생각해볼 수 있다. (있지만..! 어려움)

BST에서 root값은 왼쪽 자식보다 크고 오른쪽 자식보다 작다. 

따라서 DFS를 계속 돌면서 root값이 high보다 크면 범위에 들어오지 않으므로 버리고 왼쪽으로, low 보다 작으면 그것도 버리고 오른쪽으로 트리밍한다.

값이 low와 high 사이에 있다면 왼쪽과 오른쪽에 각각 트리밍 된 트리를 붙여주면 된다.