52. Range Sum of BST

🎯 leetcode - 938. Range Sum of BST

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 52번 문제

📌 날짜

2020.02.22

📌 시도 횟수

1 try

💡 Code

class Solution:
    value = 0

    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if root:
            if root.val >= low and root.val <= high:
                self.value += root.val
            self.rangeSumBST(root.left, low, high)
            self.rangeSumBST(root.right, low, high)

        return self.value

💡 문제 해결 방법

- 브루트 포스 + 재귀구조 DFS를 이용해서 풀었다.
- 탐색 순서는 DFS를 따르고, 탐색 도중에 low <= root.val <= high 인 값을 만나면
합을 구하는 클래스 변수(value)에 값을 더해 누적시켰다.

- 좀 더 최적화가 필요하다⭐⭐⭐❗❗

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. DFS 재귀 + 가지치기

• 가지치기 : low, high 조건에 해당 되지 않는 가지를 쳐내서 탐색에서 배제시키는 방법!'

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        def dfs(node:TreeNode):
            if not node:
                return 0 # 더해지는 값이 없도록 0을 리턴
            
            # 조건에 해당 되지 않는 가지를 끊고 탐색에서 배제
            if node.val < low:
                return dfs(node.right) # 왼쪽(더 작은 값)을 탐색에서 배제
            elif node.val > high:
                return dfs(node.left) # 오른쪽(더 큰 값)을 탐색에서 배제
            
            # low <= node.val <= high라면 값을 누적하고 탐색을 계속
            return node.val + dfs(node.left) + dfs(node.right)
        
        return dfs(root)

💡 문제 해결 방법

- 불필요한 탐색을 배제시키는 코드를 추가함

⭐ 만약 현재 노드의 값이 low보다 작을 경우,
=> 더이상 현재 노드보다 왼쪽의 노드는 탐색하지 않아도 됨
=> return dfs(node.right)으로 오른쪽만 탐색을 진행함

⭐ 만약 현재 노드의 값이 high보다 클 경우,
=> 더이상 현재 노드보다 오른쪽의 노드는 탐색하지 않아도 됨
=> return dfs(node.left)으로 왼쪽만 탐색을 진행함

---

📌 둘. 반복구조 DFS/BFS

✔ DFS 반복구조

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        stack, sum = [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:
                    sum += node.val
        return sum

✔ BFS 반복구조

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        queue, sum = [root], 0
        while queue:
            node = queue.pop(0)
            if node:
                if node.val > low:
                    queue.append(node.left)
                if node.val < high:
                    queue.append(node.right)
                if low <= node.val <= high:
                    sum += node.val
        return sum

💡 문제 해결 방법

- 조건문을 통해 불필요한 탐색을 배제시켰다.
- DFS, BFS 반복 구조의 차이점은 pop()을 앞에서 했는지, 뒤에서 했는지의 차이이다.
- 재귀보다 반복 구조가 좀 더 직관적으로 이해하기 쉬운 것 같다.

💡 새롭게 알게 된 점

if low <= node.val <= high:
- 파이썬에서 이런 코드가 가능하다는 사실을 오늘 처음 알았다...🤯

---