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

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

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

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

문제 정의

로그 재정렬 기준

책에서 구현된 코드

# 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를 더 활용하자

from http://pythaac.tistory.com/124 by ccl(A) rewrite - 2021-08-04 16:26:25