题目要求
Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).For example, given a 3-ary tree:We should return its level order traversal:[ [1], [3,2,4], [5,6]] Note:The depth of the tree is at most 1000.The total number of nodes is at most 5000.对N叉树进行水平遍历，并输出每一行遍历的结果。
思路和代码
这个和一般的水平遍历有所区别，因为它会记录每一行的水平遍历结果分别存在结果数组相应行。因此首先可以用水平遍历的通用解法，即队列的方式，进行解决：
public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(root != null) { LinkedList<Node> queue = new LinkedList<Node>(); queue.offer(root); //下一行的元素数量 int next = 1; List<Integer> levelOrderPerHeight = new ArrayList<Integer>(); while(!queue.isEmpty()) { next--; Node tmp = queue.poll(); levelOrderPerHeight.add(tmp.val); if(tmp.children != null && !tmp.children.isEmpty()) { for(Node child : tmp.children) { queue.offer(child); } } //当前行遍历完成，则更新当前行 if(next == 0) { result.add(levelOrderPerHeight); levelOrderPerHeight = new ArrayList<Integer>(); next = queue.size(); } } } return result; }上面的实现中使用next值来记录下一行的元素的个数。但是其实因为结果是采用List<List>的形式来记录的，也就是第i层的水平遍历的结果会记录于数组下标i-1的位置上。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。
public List<List<Integer>> levelOrder2(Node root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); levelOrder(root, result, 0); return result; } public void levelOrder(Node root, List<List<Integer>> result, int level) { if(root == null) return; if(level == result.size()) { result.add(new ArrayList<>()); } List<Integer> tmp = result.get(level); tmp.add(root.val); for(Node child : root.children) { levelOrder(child, result, level+1); } }