[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

Binary Tree든, N-Tree든 단순 트리 탐색 문제는 너무나 많이 접해서 모두가 쉽게 풀 수 있을 것이다. "N-Tree level order traversal"이라는 제목만 보고 오늘 문제는 너무나 쉽구나라고 느꼈다. 지하철 타고 가면서 모바일로 코딩했음에도 전혀 어렵다고 느껴지지 않았다.

Tree 탐색은 recursion을 이용해서 풀면 되면 recursion할 함수에 level을 넣어줘 해당하는 level list에 탐색하고 있는 노드의 값을 추가하기만 하면 된다. 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);
		}
	}
}

Solution의 멤버 변수로 return할 값을 생성한 뒤, 노드 탐색을 할 때 level에 해당하는 list가 없으면 생성해주기만 하면 된다.

Reference

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