Description:
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-叉樹,傳回其層次周遊的節點值;
解法:不管是二叉樹還是N叉樹,對于層次周遊我們都可以利用隊列來實作;算法流程如下:
- 首先,将根節點入隊
- 當隊列不為空時,計算目前隊列長度,即目前層節點數
- 取出目前層所有節點,并且将其孩子節點入隊
- 繼續第2步直到隊列為空
Java
/*
// 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;
Deque<Node> nodes = new ArrayDeque<>();
nodes.addLast(root);
while (!nodes.isEmpty()) {
int len = nodes.size();
List<Integer> temp = new ArrayList<>();
while (len-- > 0) {
Node node = nodes.removeFirst();
temp.add(node.val);
for (int i = 0; i < node.children.size(); i++) {
nodes.addLast(node.children.get(i));
}
}
result.add(temp);
}
return result;
}
}