938. Range Sum of BST

👩‍💻 문제

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

 

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

 

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
 

Constraints:
The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 105
1 <= low <= high <= 105
All Node.val are unique.

 

 

💡 풀이 #1

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        res = []
        def traversal(node):      # 재귀적으로 트리를 순회하면서 주어진 범위 내에 있는 노드들의 값을 res 리스트에 추가
            if node is None:
                return
            if low <= node.val <= high:   #low, high 사이에 있는 값이면, 더해줘야하니까 append
                res.append(node.val)
            if low < node.val:            #low보다 큰 값이면, 왼쪽에 있는 현재 노드보다 작은 값들 순회
                traversal(node.left)
            if node.val < high:           #high보다 작은 값이면, 오른쪽에 있는 현재 노드보다 큰 값들 순회
                traversal(node.right)
        traversal(root)
        return sum(res)                 #주어진 범위를 벗어나지 않은 값들만 합산

 

 

💡 풀이 #2 

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        stack = [root]      #root를 stack 형태로 만들어준다 
        range_sum = 0
        while stack:        #stack이 비어있지 않은 동안에 
            node = stack.pop()  #stack의 마지막 값을 return한 값이 node이다 
            if node:
                if low < node.val: #가장 위에 있는 값을 뽑아낸 node.val > low면 더 작은 값이면 왼쪽으로 순회한다
                    stack.append(node.left)
                if node.val < high: #가장 위에 있는 값이 high보다 작으면 더 큰값인 오른쪽으로 순회한다
                    stack.append(node.right)
                if low <= node.val <= high: # 그렇게 해서 크거나 같고, 작거나 같은 값을 만나면 드디어 그걸 더한다 
                    range_sum += node.val

        return range_sum

 

✍️ 해설

왼쪽은 더 작은 값, 오른쪽은 더 큰 값이 위치한다.

어쨌든 트리의 모든 노드를 순회하면서, 범위 내의 값을 찾을 것이기 때문에

low, high의 범위 내에서, low보다 크기만 하면 low와 같은 값도 있을 수 있기 때문에 왼쪽 자식노드(더 작은 값이 있는 쪽)으로 순회

high보다 작기만 하면 그 반대로 high와 같은 값이 있을수도 있는 오른쪽 자식 노드(더 큰 값이 있는 쪽)으로 순회

그러다 마침내 low보다 크거나 같고, high보다 작거나 같은 값을 마주치면, 그걸 최종 result에 더해준다

 

if node: 

이 부분은 현재 노드가 None이 아닌지 확인하는 역할이다. None이면 자식노드도 당연히 없을거니까, 아무런 동작을 하지 않고 다음 노드를 처리하는 것. 

 

🥳 배운점

이진트리의 전위, 중위, 후위 순회 중 편한 것으로 순회해야 한다는 점.

트리 구조를 코드하는 법을 처음 문제로 풀어보면서 배웠다.

node.val 이라고 쓰는구나! ?!