[leetcode]102. Binary Tree Level Order Traversal (이진트리, BFS)

102. Binary Tree Level Order Traversal

난이도: Medium

관련 토픽: 이진 트리, BFS

문제 설명

이진 트리의 루트 노드가 주어질 때, 노드의 값을 레벨 순서대로 탐색한 결과를 반환하는 문제입니다.

즉, 트리의 각 레벨을 왼쪽에서 오른쪽으로 순차적으로 탐색하여 노드의 값을 반환해야 합니다.

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

입력 및 출력 예시

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []

 

---

문제 풀이 

이 문제는 트리를 BFS (Breadth-First Search, 너비우선탐색) 방식으로 탐색하는 대표적인 유형입니다.

 

트리의 배열 표현

문제에서 제공하는 Input은 이진 트리 형태를 배열로 표현하는 방식입니다. 이진 트리를 배열로 표현할 때는 다음과 같은 규칙을 따릅니다.

 

• 왼쪽 자식: 2 * i + 1
• 오른쪽 자식: 2 * i + 2
• 여기서 i는 부모 노드의 인덱스

따라서 위의 [3,9,20,null,null,15,7]는 9의 index는 1이고 왼쪽 자식은 2 * 1 + 1, 오른쪽 자식은 2 * i + 2로 표현됩니다. 9는 자식 노드가 없기 때문에 각 각 null로 표현됩니다. 또한 배열 마지막의 null은 생략될 수 있습니다.

 

 

배열 표현은 단순히 트리를 직관적으로 나타내기 위한 표기법입니다. 실제로 함수로 전달되는 입력값은 TreeNode 형태의 연결된 트리 구조입니다. val, left, right로 val은 현재 노드의 값, left는 왼쪽 노드, right는 오른쪽 노드입니다.

 

문제 해결 전략

이 문제는 이진 트리 root 노드에서 시작하여 해당 트리를 전부 순회하는데, 트리의 레벨 단위로 노드의 값을 저장합니다.

레벨 단위로 값을 저장하기 때문에 깊이가 아닌 너비로 탐색을 진행해야 합니다.

따라서 BFS를 활용하고 BFS에서는 queue를 사용하여 데이터를 탐색합니다.

코드를 보겠습니다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val);
 *     this.left = (left===undefined ? null : left);
 *     this.right = (right===undefined ? null : right);
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];

  const result = []; // 결과를 저장할 배열
  const queue = [root]; // BFS 탐색을 위한 큐 초기화

  while (queue.length > 0) {
    const levelSize = queue.length; // 현재 레벨의 노드 개수
    const levelList = []; // 현재 레벨의 값을 저장할 배열

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift(); // 큐에서 노드를 꺼내 처리

      levelList.push(node.val); // 현재 노드의 값을 저장
      if (node.left) queue.push(node.left); // 왼쪽 자식 추가
      if (node.right) queue.push(node.right); // 오른쪽 자식 추가
    }

    result.push(levelList); // 현재 레벨의 결과를 전체 결과에 추가
  }
  return result; // 최종 결과 반환
};

 

 

초기 조건 처리

• const result = [];: 결과를 저장할 배열입니다.
• if (!root) return [];: 루트 노드가 없는 경우, 빈 배열을 바로 반환합니다.

BFS 탐색

• 큐 초기화
  • const queue = [root];: BFS 탐색을 위해 큐에 root 노드를 추가합니다.
• 레벨별 탐색
  • while (queue.length > 0): queue는 현재 레벨의 노드들이 저장되는 곳입니다. queue가 비었다면 더 이상 탐색할 노드가 없는 것 이기 때문에 반복문을 종료합니다.
  • const node = queue.shift();: 큐의 가장 앞의 노드를 꺼냅니다.
  • levelList.push(node.val);: 현재 레벨의 val 값을 저장합니다.
• 자식 노드 추가
  • if (node.left) queue.push(node.left);: 왼쪽 자식 노드가 있으면 큐에 추가합니다.
  • if (node.right) queue.push(node.right);: 오른쪽 자식 노드가 있으면 큐에 추가합니다. 

레벨 결과 저장

• result.push(levelList);: 현재 레벨의 노드 값을 결과 배열에 추가합니다.

---

시간 및 공간 복잡도

1. 시간 복잡도
   • 모든 노드를 한 번씩 방문하므로 O(N)
   • 여기서 N은 트리의 노드 개수를 뜻합니다.
2. 공간 복잡도
   • 큐의 최대 노드 개수는 특정 레벨의 노드 개수와 같습니다.
   • 트리의 최대 너비를 W라 할 때, O(W)

---

트리 탐색과 BFS를 이해하고 적용하는 연습에 매우 적합한 문제 같습니다 ㅎㅎ