[LeetCode] 938. Range Sum of BST [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Range Sum of BST - LeetCode>

1. 문제 (이진 탐색 트리(BST) 합의 범위)

BST가 주어졌을 때 L 이상 R 이하의 값을 지닌 노드의 합을 구하라.

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
ex : 4 -> 4 + 5 + 6 + 7 + 8 = 30

2. 풀이

재귀탐색과 DFS를 이용한 풀이

반복문과 DFS를 이용한 풀이

3. 코드

• 재귀탐색과 DFS를 이용한 풀이

# 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: 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)

• 반복문과 DFS를 이용한 풀이

# 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: TreeNode, low: int, high: int) -> int:
        stack, ret = [root], 0

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

        return ret

• 결과 :

방식	Status	Runtime	Memory	Language
재귀탐색	[Accepted]	200 ms	22.3 MB	python3
반복문	[Accepted]	204 ms	22.3 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋