429. N-ary Tree Level Order Traversal.md

429. N-ary Tree Level Order Traversal

---

Difficulty : Medium

Related Topics : BFS、Tree

---

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, 10^4]

---

Solution

• mine
  • Java
    • BFS Runtime: 2 ms, faster than 92.81%, Memory Usage: 47.5 MB, less than 31.86% of Java online submissions

      // O(N)time O(N)space  N = node.count
      public List<List<Integer>> levelOrder(Node root) {
          List<List<Integer>> res = new ArrayList<>();
          List<Node> nodes = new ArrayList<>();
          nodes.add(root);
          bfs(nodes, res);
          return res;
      }
      
      void bfs(List<Node> nodes, List<List<Integer>> res){
          if(nodes == null || nodes.size() == 0) return;
      
          List<Integer> temp = new ArrayList<>();
          List<Node> tempNodes = new ArrayList<>();
          for(Node node : nodes){
              if(node == null) continue;
      
              temp.add(node.val);
              tempNodes.addAll(node.children);
          }
          if(temp.size() > 0){
              res.add(temp);
          }
          bfs(tempNodes, res);
      }
      

---

• the most votes
  • Runtime: 4 ms, faster than 53.77%, Memory Usage: 47.9 MB, less than 7.78% of Java online submissions

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new LinkedList<>();
    
        if (root == null) {
            return ret;
        }
    
        Queue<Node> queue = new LinkedList<>();
    
        queue.offer(root);
    
        while (!queue.isEmpty()) {
            List<Integer> curLevel = new LinkedList<>();
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Node curr = queue.poll();
                curLevel.add(curr.val);
                for (Node c : curr.children) {
                    queue.offer(c);
                }
            }
            ret.add(curLevel);
        }
    
        return ret;
    }
    

---