LeetCode 102 - Binary Tree Level Order Traversal (Medium)

문제

LeetCode - 102번

풀이 과정

이진 트리의 level order 탐색을 구현하는 문제입니다.
대표적인 BFS 문제로 루트 노드를 기준으로 왼쪽과 오른쪽 서브트리의 루트 노드를 방문해주며 탐색을 수행하면 됩니다.

이때 주의할점은 문제 출력 형식이 level 에 있는 모든 노드를 하나로 묶어서 배열로 추가해야하므로
각각의 BFS 단계마다 현재 큐에 존재하는 모든 노드의 개수 만큼 루프를 돌며 자식 노드들을 탐색해야한다는 것입니다.

마치 백준의 토마토 문제와 비슷한 방식이죠. 이렇게 해야 현재 레벨에 존재하는 모든 노드를 함께 배열로 묶어줄 수 있습니다.

코드

/**
 * 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 answer = [];

  function bfs(root) {
    const Q = [];
    Q.push(root);

    while (Q.length) {
      const loop = Q.length;
      const visit = [];

      for (let i = 0; i < loop; i++) {
        const here = Q.shift();
        visit.push(here.val);

        if (here.left) Q.push(here.left);
        if (here.right) Q.push(here.right);
      }

      if (visit.length) answer.push(visit);
    }
  }

  bfs(root);
  return answer;
};