102. Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal

문제

레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다.
레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.

테스트 케이스

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

풀이

level-order는 BFS 탐색과 마찬가지로 큐를 사용한다. root 레벨부터 자식인 왼쪽, 오른쪽 노드 순으로 탐색한다. 큐를 모두 탐색한 것은 곧 레벨에 더이상 탐색할 노드가 없다는 것이므로 result에 group을 담아준다.

/**
 * 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 === null) return []

  const result = []
  const queue = [root]

  while (queue.length > 0) {
    const size = queue.length
    const group = [];

    for (let i = 0; i < size; i++) {
      const curr = queue.shift();
      group.push(curr.val)

      if (curr.left) queue.push(curr.left)
      if (curr.right) queue.push(curr.right)
    }

    result.push(group)
  }

  return result
};

출처

• 트리 순회 | wiki