[파이썬] 938. Range Sum of BST - 리트코드

문제

이진 탐색 트리의 노드와 두 개의 정수 low와 high 가 주어지면 포함 범위 에 있는 값을 가진 모든 노드의 값 합계를 반환하는 코드를 구현하시오.

입력

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.

작성한 코드1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(node:TreeNode):
        	# 노드 값이 없으면 0을 반환
            if not node:
                return 0
            
            # low 값보다 작으면 오른쪽 노드들만 확인
            if node.val < low:
                return dfs(node.right)
            # high 값보다 작으면 왼쪽 노드들만 확인
            elif node.val > high:
                return dfs(node.left)
            
            # 위에서 해당하는 포함하는 값만 재귀호출해서 return 해주기 때문에
            # 이 부분에서는 현재 값 + 오른쪽 값 + 왼쪽값을 더해주면 됌.
            return node.val + dfs(node.right) + dfs(node.left)
        
        return dfs(root)

 

작성한 코드2

def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return 0
        return (root.val if low <= root.val <= high else 0) + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

이 방법이 좀 더 이해하기가 쉬운 방법인거 같다.

root.val 값을 확인해서 사이에 있으면 root.val값과 왼쪽 오른쪽도 확인한 결과 값들을 더해 주면 최종적으로 low와 high사이에 포함하는 값이 나오는 방식이다.

https://leetcode.com/problems/range-sum-of-bst/

Range Sum of BST - LeetCode