摘要：題目要求對叉樹進行水平遍歷，并輸出每一行遍歷的結(jié)果。因此無需再用隊列來額外存儲每一行的水平遍歷，可以直接通過遞歸將遍歷結(jié)果插入到相應行的結(jié)果集中。
題目要求
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叉樹進行水平遍歷，并輸出每一行遍歷的結(jié)果。
思路和代碼
這個和一般的水平遍歷有所區(qū)別，因為它會記錄每一行的水平遍歷結(jié)果分別存在結(jié)果數(shù)組相應行。因此首先可以用水平遍歷的通用解法，即隊列的方式，進行解決：
public List> levelOrder(Node root) {
List> result = new ArrayList>();
if(root != null) {
LinkedList queue = new LinkedList();
queue.offer(root);
//下一行的元素數(shù)量
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;
}
上面的實現(xiàn)中使用next值來記錄下一行的元素的個數(shù)。但是其實因為結(jié)果是采用List的形式來記錄的，也就是第i層的水平遍歷的結(jié)果會記錄于數(shù)組下標i-1的位置上。因此無需再用隊列來額外存儲每一行的水平遍歷，可以直接通過遞歸將遍歷結(jié)果插入到相應行的結(jié)果集中。
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);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/74290.html
