429. N-ary Tree Level Order Traversal

문제

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

n-ary 트리가 지정된 경우 해당 노드 값의 수준 순서 통과를 반환합니다.
Nary-Tree 입력 직렬화는 레벨 순서 순회(traversal)로 표현되며, 각 자식 그룹은 null 값으로 구분됩니다(예제 참조).

 

예시

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

 

제약 조건

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 104]

 

해결 과정

BFS 함수로 재귀를 통해 문제를 해결해나간다.

depth가 res.length일 때, 2차 배열을 생성해야 하므로 먼저 빈 배열을  push 한다.

depth 인덱스의 배열에 node.val을 push한다.

for문을 돌며 나머지 children에게 BFS 재귀 함수를 호출한다.

 

해결 코드

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const res = [];
    BFS(root, 0);
    return res;
    
    function BFS(node, depth) {
        if (!node) return;
        if (depth === res.length) {
            res.push([]);
        }
        res[depth].push(node.val);
        for (child of node.children) {
            BFS(child, depth + 1);
        }
    }
};