Python으로 푸는 LeetCode 938. Range Sum of BST (Easy)

BST(이진 탐색 트리)가 있다.

입력받은 L, R의 범위에 속하는 값들의 합을 반환하는 

프로그램을 짜시오.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

트리는 깊이가 있는 자료 구조이므로 개인적으로 나는 재귀로 문제를 해결하기가 쉽다. 나는 Node를 인자 값으로 넘기면 그 노드를 root로 하는 이진 탐색트리에서 L, R을 범위로 하는 Node를 찾아 값을 더하고 그 결과값을 반환해주는 checkChildBST라는 함수를 만들었다. 이런 재귀 함수를 짤 때에 가장 중요한 것은 재귀를 언제 중단하느냐에 대한 조건을 반드시 명시하는 것이라고 생각한다. 내 코드에서는 총 2번의 반환 작업이 일어난다.

- 현재의 노드가 아무런 자식을 가지고 있지 않은 leaf node일 경우에 결과 값을 반환한다. (24번째 줄)

- 현재 root의 val에 대해서 모든 가능성을 다 탐색하고 난 후의 결과 값을 반환한다(42번째 줄)

파이썬 코드

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
def _insert_node_into_binarysearchtree(node, data):
    if node == None:
        node = TreeNode(data)
    else:
        if (data <= node.val):
            node.left = _insert_node_into_binarysearchtree(node.left, data);
        else:
            node.right = _insert_node_into_binarysearchtree(node.right, data);
    return node
 
 
 
class Solution:
    def checkChildBST(self, root, result, l, r):
 
        # if leaf node, recursion must be closed
        if root == None:
            return result
 
        if root.val <= l:
            if root.val == l:
                result += root.val
            result = self.checkChildBST(root.right, result, l, r)
 
        if r <= root.val:
            if r == root.val:
                result += root.val
            result = self.checkChildBST(root.left, result, l, r)
 
        if l < root.val < r:
            result = self.checkChildBST(root.left, result + root.val, l, r)
            result = self.checkChildBST(root.right, result, l, r)
 
        # Returns the result of the tree of child
        return result
 
 
    def rangeSumBST(self, root, L: int, R: int) -> int:
        return self.checkChildBST(root, 0, L, R)
 
 
if __name__ == "__main__":
    root = _insert_node_into_binarysearchtree(None, 10)
    node = _insert_node_into_binarysearchtree(root, 5)
    node = _insert_node_into_binarysearchtree(root, 15)
    node = _insert_node_into_binarysearchtree(root, 3)
    node = _insert_node_into_binarysearchtree(root, 7)
    node = _insert_node_into_binarysearchtree(root, 18)
    node = _insert_node_into_binarysearchtree(root, 1)
    node = _insert_node_into_binarysearchtree(root, 6)
 
    s = Solution()
    print(s.rangeSumBST(root, 7, 15))
    print(s.rangeSumBST(root, 6, 10))