출처 : 파이썬 알고리즘 인터뷰

3일동안 야무지게 놀았으니까 오늘은 두 문제 풀어야징

오늘의 문제 1

leetcode 226.Invert Binary Tree

주어진 이진트리를 반전해서 반환하는 문제로, 전에 DFS 깰 때 한번 했었다.

BSF로도 풀 수 있다는 사실!

생각의 흐름

DFS로 풀때는 가장 말단 노드까지 들어가서 반전시키면서 빠져나오는 방식이었다

BFS는 반전시키면서 깊어지는 느낌으로 풀이 가능

접근 1

BFS 구현은 주로 queue로 함

queue = collections.deque([root])

while queue:
  node = queue.popleft()

접근 2

반전시키면서 내려가기 권법

if node:
  node.right, node.left = node.left, node.right
  
  queue.append(node.left)
  queue.append(node.right)
  
return root

1번 문제 최종 코드

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
  queue = collections.deque([root])
  
  while queue:
    node = queue.popleft()
    if node:
      node.right, node.left = node.left, node.right

      queue.append(node.left)
      queue.append(node.right)
   
return root

오늘의 문제 2

leetcode 938. Range Sum of BST

이진탐색트리를 탐색하면서 주어진 범위 내에 해당되는 노드들의 합을 반환하는 문제이다.

이것도 DFS로 풀 수 있고, BFS로 풀 수 있기 때문에 한 방법씩 깨보기로 하겠다.

생각의 흐름

가장 말단으로 가서 올라오면서 값에 해당하면 더하기 = 브루트포스와 비슷한 효율일듯..? 굳이?

-> 이진탐색트리의 특성(왼쪽자식<부모<오른쪽자식)을 이용해서 분기하는거 어떤데

-> 좋은데

DFS

최종코드

DFS로 풀이해보자

def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
  def dfs(node):
    if not node : return

    # 부모 값이 low보다도 작으면 더 큰 오른쪽 자식 탐색
    if node.val < low: return dfs(node.right)
    # 부모 값이 right보다 크면 더 작은 왼쪽 자식 탐색
    if node.val > high: return dfs(node.left)

    return node.val + dfs(node.left) + dfs(node.right)

BFS

최종코드

BFS로 풀기 위해 queue 사용

def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
  queue = collections.deque([root])
  sum = 0

  while queue:
    node = queue.popleft()
    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