[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리 합의 범위

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

로그 재정렬 기준

1.  

 

책에서 구현된 코드

# 1. 재귀
class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        def dfs(node: TreeNode):
            if not node:
                return 0

            if node.val < L:
                return dfs(node.right)
            elif node.val > R:
                return dfs(node.left)
            return node.val + dfs(node.left) + dfs(node.right)

        return dfs(root)
        
# 2. stack (DFS)
class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        stack, sum = [root], 0
        # 스택 이용 필요한 노드 DFS 반복
        while stack:
            node = stack.pop()
            if node:
                if node.val > L:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
                if L <= node.val <= R:
                    sum += node.val
        return sum
        
# 3. queue (BFS)
class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        stack, sum = [root], 0
        # 큐 연산을 이용해 반복 구조 BFS로 필요한 노드 탐색
        while stack:
            node = stack.pop(0)
            if node:
                if node.val > L:
                    stack.append(node.left)
                if node.val < R:
                    stack.append(node.right)
                if L <= node.val <= R:
                    sum += node.val
        return sum

 

기억해야할 기법

• Stack / Queue를 이용한 반복구조
  
  • 재귀만 사용하는 버릇이 생긴듯
  • Stack / Queue를 이용한 구조도 익혀두자

 

내가 구현한 코드

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        if root:
            if root.val > high:
                sum = self.rangeSumBST(root.left, low, high)
            elif root.val < low:
                sum = self.rangeSumBST(root.right, low, high)
            else:
                sum = self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high) + root.val
            return sum

        return 0

• 재귀보다 stack/queue를 사용한 구조가 일반적으로 더 빠르다고 함
• stack/queue를 더 활용하자