Algorithm


Problem Name: 429. N-ary Tree Level Order Traversal

Problem Link: https://leetcode.com/problems/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).

 

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]

 
 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public List();
    }
    List();
    Queue queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
      int size = queue.size();
      List < Integer> currLevel = new ArrayList<>();
      while (size-- > 0) {
        Node removed = queue.remove();
        currLevel.add(removed.val);
        queue.addAll(removed.children);
      }
      levels.add(currLevel);
    }
    return levels;
  }   
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [1,null,3,2,4,null,5,6]

Output

x
+
cmd
[[1],[3,2,4],[5,6]]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const levelOrder = function(root) {
  const res = []
  if(root == null) return res
  helper(root, 0, res)
  return res
};

function helper(node, index, res) {
  if(node == null) return
  if(res[index] == null) res[index] = []
  res[index].push(node.val)
  for(let i = 0, len = node.children.length; i < len; i++) {
    helper(node.children[i], index + 1, res>
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [1,null,3,2,4,null,5,6]

Output

x
+
cmd
[[1],[3,2,4],[5,6]]

#3 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0429_NAryTreeLevelOrderTraversal
    {
        public IList < IList<int>> LevelOrder(Node root)
        {
            var results = new List < IList<int>>();
            if (root == null) return results;

            var queue = new Queue < Node>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                var size = queue.Count;
                var result = new List < int>();
                for (int i = 0; i  <  size; i++)
                {
                    var node = queue.Dequeue();
                    result.Add(node.val);
                    if (node.children != null)
                        foreach (var child in node.children)
                            queue.Enqueue(child);
                }

                results.Add(result);
            }

            return results;
        }

        public class Node
        {
            public int val;
            public IList < Node> children;

            public Node() { }

            public Node(int _val)
            {
                val = _val;
            }

            public Node(int _val, IList < Node> _children)
            {
                val = _val;
                children = _children;
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

x
+
cmd
[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
Advertisements

Demonstration


Previous
#427 Leetcode Construct Quad Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#430 Leetcode Flatten a Multilevel Doubly Linked List Solution in C, C++, Java, JavaScript, Python, C# Leetcode