摘要：题目要求对叉树进行水平遍历，并输出每一行遍历的结果。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。
题目要求
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> levelOrder(Node root) {
List> result = new ArrayList>();
if(root != null) {
LinkedList queue = new LinkedList();
queue.offer(root);
//下一行的元素数量
int next = 1;
List levelOrderPerHeight = new ArrayList();
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();
next = queue.size();
}
}
}
return result;
}
上面的实现中使用next值来记录下一行的元素的个数。但是其实因为结果是采用List的形式来记录的，也就是第i层的水平遍历的结果会记录于数组下标i-1的位置上。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。
public List> levelOrder2(Node root) {
List> result = new ArrayList>();
levelOrder(root, result, 0);
return result;
}
public void levelOrder(Node root, List> result, int level) {
if(root == null) return;
if(level == result.size()) {
result.add(new ArrayList<>());
}
List tmp = result.get(level);
tmp.add(root.val);
for(Node child : root.children) {
levelOrder(child, result, level+1);
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/74290.html
