2021-02-02] Trim a Binary Search Tree

오늘의 문제: leetcode.com/problems/trim-a-binary-search-tree/

Trim a Binary Search Tree - LeetCode

 

이번 문제는 BST 에서 필요한 부분을 나눠주는 부분이다.

 

아래 예제를 보자

 

입력값으로 주어지는 root, low,high로 root Node안에서 low, high 사이의 값만 남기고 나머지는 제거하는 문제이다.

 

low, high 경계 밖의 값을 제거하면서, BST를 만족해야한다. ( 최초 주어지는 Tree 또한 BST를 만족 )

 

만약 low보다 작으면, 오른쪽의 Node를 가져오고, 경계값보다 크면 왼쪽의 Node을 붙여주면 된다.

 

아래 코드로 이해해 보자.

 

class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        def trim(node):
            if not node:
                return node # None인 경우 None return
            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)