[leetcode #429] N-ary Tree Level Order Traversal

Problem

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).
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]

Idea

二叉木でもN叉木でも、簡単な木検索で問題が接触しすぎて、みんなが簡単に解くことができます.「N-Tree level order遍歴」というテーマだけを見て、今日の問題は簡単すぎると思います.地下鉄に乗る時、携帯電話のコードを使っても何の困難も感じません.
Treeナビゲーションは、再帰を使用して解くだけで、再帰する関数にレベルを追加し、対応するレベルリストにナビゲーション中のノードの値を追加できます.pseudo-codeは以下の通りです.

fun traverseNode(Node node, Int level) { 
	(n-level list).add(node.val)
	for(Node child: node.children)
		traverseNode(child, level+1)

Solution

class Solution {
	List<List<Integer>> res = new ArrayList<>();

	public List<List<Integer>> levelOrder(Node root) {
		traverseNode(root, 1);
		return res;
	}

	private void traverseNode(Node node, int level){
		if (node == null)
			return;
		if (res.size() < level)
			res.add(new ArrayList<>());
		res.get(level-1).add(node.val);
		for (Node child : node.children){
			traverseNode(child, level+1);
		}
	}
}

ソリューションのメンバー変数として、返す値を作成し、ノードをナビゲートするときにlevelに対応するリストがない場合は、その値を作成するだけです.

Reference

https://leetcode.com/problems/n-ary-tree-level-order-traversal/