[리트코드] 938. 이진 탐색 트리(BST) 합의 범위 (Python)

Range Sum of BST - LeetCode

문제

이진 탐색 트리의 노드와 두 개의 정수 low와 high 가 주어지면 포함 범위 에 있는 모든 노드의 합을 구하라.

과정

• DFS를 이용하여 풀어준다.

 

입력

root = [10,5,15,3,7,null,18], low = 7, high = 15

출력

32

 

풀이

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

            return node.val + dfs(node.left) + dfs(node.right)
        
        return dfs(root)

 

한 줄 씩 해석해보기

def dfs(node):
    if not node:
        return 0

• dfs함수를 만들고 node라는 변수를 널어준다.
• 만약 노드가 없다면 0을 return한다

    if node.val < low:
        return dfs(node.right)
    if node.val > high:
        return dfs(node.left)

• 만약 노드의 값이 low보다 작다면 dfs함수에 해당 노드의 오른쪽 값을 넣어준다.
• 만약 노드의 값이 high보다 크다면 dfs함수에 해당 노드의 왼쪽 값을 넣어준다.

    return node.val + dfs(node.left) + dfs(node.right)

• node의 값과 왼쪽 부터 오른쪽 값을 모두 더한 후 return해준다.

return dfs(root)

• dfs에 root를 넣고 함수를 시작한다.