Question:

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

We should return its level order traversal:
[
     [1],
     [3,2,4],
     [5,6]
]

Note:

  1. The depth of the tree is at most 1000.
  2. The total number of nodes is at most 5000.

Solution:

  • Method 1: bfs 
      /*
  // Definition for a Node.
  class Node {
      public int val;
      public List<Node> children;
    
      public Node() {}
    
      public Node(int _val,List<Node> _children) {
          val = _val;
          children = _children;
      }
  };
  */
  class Solution {
      public List<List<Integer>> levelOrder(Node root) {
          List<List<Integer>> result = new ArrayList<>();
          if(root == null) return result;
          Queue<Node> q = new LinkedList<>();
          q.offer(root);
          while(!q.isEmpty()){
              List<Integer> temp = new ArrayList<>();
              int size = q.size();
              for(int i  = 0; i < size; i++){
                  Node node = q.poll();
                  temp.add(node.val);
                  for(Node n : node.children){
                      q.offer(n);
                  }
              }
              result.add(temp);
          }
          return result;
      }
  }