이진트리 추가문제

Question 1: Trim a Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

입력: root = [3,0,4,null,2,null,null,1], low = 1, high = 3

출력: [3,2,null,1]

내 풀이

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

• 노드의 값이 low 보다 작으면 왼쪽 자식노드 또한 마찬가지로 low 보다 작을 것이므로 검사할 필요가 없다.
• 노드의 값이 high 보다 크면 오른쪽 자식노드 또한 마찬가지로 high 보다 클 것이므로 검사할 필요가 없다.

결과

Runtime: 109 ms, faster than 6.73% of Python3 online submissions for Trim a Binary Search Tree. Memory Usage: 18 MB, less than 57.48% of Python3 online submissions for Trim a Binary Search Tree.