共计 1464 个字符,预计需要花费 4 分钟才能阅读完成。
题目要求
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);
}
}
正文完