102. Binary Tree Level Order Traversal

문제링크: https://leetcode.com/problems/binary-tree-level-order-traversal/

이진트리의 레벨별 노드값들을 배열로 그룹화해 반환하는 문제다.

Solution

BFS

깊이별로 노드를 분할하기 때문에 노드 탐색알고리즘 중 BFS를 사용했다. 탐색할 때 노드와 레벨 정보를 함께 넣어 현재 노드의 깊이를 알 수 있게 한다.

Algorithm

• BFS를 위한 queue를 정의한다.
• queue는 [root, node]의 정보를 담고 있다.
• queue순회를 통해 result[level]에 있는 배열에 노드값을 추가한다.

var levelOrder = function(root) {
  // bfs
  if (root === null) return [];
  
  const queue = [];
  queue.push([root, 0]); // push node , level
  const result = [];
  
  while (queue.length) {
    const [curRoot, level] = queue.shift();
    result[level] ? result[level].push(curRoot.val) : result[level] = [curRoot.val];
    if (curRoot.left) queue.push([curRoot.left, level + 1]);
    if (curRoot.right) queue.push([curRoot.right, level + 1]);
  }
  
  return result;
};

DFS

깊이 정보만 전달할 수 있다면 깊이 우선탐색을 통해서도 충분히 구현할 수 있다. 그리고 중간에 최적해를 구하는 문제가 아니기 때문에 DFS를 사용해도 큰 문제가 없다.

Algorithm

• DFS 재귀 함수는 루트와 깊이 정보를 받는다.
• 루트가 null이 아닌지 판단하고 자식들을 갱신한 레벨과 함께 재귀 한다.
• 각 노드를 탐색할 때마다 노드값을 BFS와 동일하게 result에 넣는다.

var levelOrder = function(root) {
  // dfs
  const result = [];
  
  const dfsWithLevel = (rt, level) => {
    if (!rt) return;
    result[level] ? result[level].push(rt.val) : result[level] = [rt.val];
    dfsWithLevel(rt.left, level + 1);
    dfsWithLevel(rt.right, level + 1);
  }
  
  dfsWithLevel(root, 0);
  return result;
};