938. Range Sum of BST (Tree, Depth-First Search, Binary Search Tree, Binary Tree)

링크 - https://leetcode.com/problems/range-sum-of-bst/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

DFS로 탐색하며 값을 비교하면서 풀 수 있는 문제이다.

또한 BST이기 때문에 현재 node의 val이 low보다 크면 왼쪽 child를 탐색하고, node의 val이 high보다 작으면 오른쪽 child를 탐색하면 시간을 줄일 수 있다.

Code

# Recursive
# 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:
        ans = 0

        def dfs(node):
            if not node:
                return

            nonlocal ans

            val = node.val
            if low <= val <= high:
                ans += val

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

        dfs(root)
        return ans
        
# Iterative
class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        ans = 0
        stack = [root]

        while stack:
            node = stack.pop()
            if node:
                val = node.val
                if low <= val <= high:
                    ans += val
                if low < val:
                    stack.append(node.left)
                if val < high:
                    stack.append(node.right)

        return ans

Complexity

Time Complexity: O(n) 여기서 n은 Tree의 node 개수이다

Space Complexity: O(n) dfs이기 때문에 function call stack을 유지하고 있으므로 이때의 worst case는 O(n)이다.