tree 구조 알고리즘 풀기(DFS, BFS)

leetCode에서 문제를 풀다가 DFS와 BFS에 대해서 한번 더 정리해보고자 블로깅을 하게 되었다.

문제는 아래와 같다.

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

문제는 간단하다.

tree구조가 있을 때 같은 깊이(level)에 있는 노드 끼리 같은 배열에 담는다.
그리고 level을 역순으로 하여 최종적으로 이들을 담고 있는 배열을 반환하면 된다.

이 문제에는 2가지 풀이법이 존재한다.

DFS와 BFS를 이용한 방법이다.

BFS란? (너비 우선 탐색)

BFS

위키 백과를 보면 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이라고 소개하고 있다.

즉, 같은 깊이(level)에 위치한 모든 노드들을 방문한 후 다음 깊이로 내려간다고 보면 된다.

그러면 해당 방법을 이용해서 위의 문제를 풀어보자.

level별로 탐색을 하면서 value와 자식 노드들을 탐색하여 푸는 방식이다.

콘솔로 찍어 보아도 같은 level을 다 탐색한 후 자식노드들을 탐색함을 확인할 수 있다. ( 3, 9, 20, 15, 7 )

이 문제를 풀 때는 BFS를 이용한 방법이 가장 먼저 떠오르고 무난하게 풀 것 같다. 다음으로 DFS를 이용해 풀어보자.

DFS란? (깊이 우선 탐색)

DFS

말 그대로 깊이를 우선시 하여 탐색하는 것이다. 해당 노드를 탐색할 때 깊이의 끝에 다다를 때까지 탐색한 후 다음 노드를 탐색하는 것이다.

이미지를 참고하면 BFS와 확연히 어떻게 다른지 알 수 있을 것이다.

사실 문제를 풀고 나서 더 간결하고 좋은 방법을 공부하기 위해 다른 사람의 풀이를 보는데, DFS를 이용한 풀이가 있어 매우 인상적이었다.

level(깊이)를 result의 index로 분류하여 반환하는 방법이다.

실제로 8번째 줄의 node.val를 찍어 보니 DFS방식으로 tree를 순환함을 확인할 수 있다. ( 3, 9, 20, 15, 7 )

Easy에 랭크된 문제이지만 트리의 구조라던지 트리 순환 방식에 한번 더 생각해보게 되는 문제라 좋았다.

꾸준히 알고리즘을 풀자..!