這是悅樂書的第225次更新檐嚣，第238篇原創(chuàng)
01 看題和準備
今天介紹的是LeetCode算法題中Easy級別的第92題（順位題號是429）。給定n-ary樹啰扛，返回其節(jié)點值的級別順序遍歷嚎京。（即嗡贺，從左到右，逐級）鞍帝。例如诫睬，給定一個3-ary樹：
我們應該返回它的級別順序遍歷：
[[1]，[3,2,4][5,6]]
注意：
樹的深度最多為1000帕涌。
節(jié)點總數(shù)最多為5000摄凡。
本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8宵膨，環(huán)境是win7 64位系統(tǒng)架谎，使用Java語言編寫和測試。
02 第一種解法
使用廣度優(yōu)先算法（BFS）辟躏，一級一級谷扣，從左往右遍歷，對此我們借助隊列來實現(xiàn)捎琐。
特殊情況：當root為null時会涎，直接返回一個沒有任何元素的list。
正常情況：先將root放入隊列瑞凑，然后開始循環(huán)末秃，最外層循環(huán)，我們新建一個list籽御，存入每一級的元素练慕，第二層循環(huán)開始處理隊列中上一輪被添加進去的node，依次poll出來技掏，將其val存入外層循環(huán)新建的list中铃将，而其另一個屬性children，因為是一個以node為元素的數(shù)組哑梳，所以在此使用for-each循環(huán)劲阎，將其添加進隊列中，在下一輪循環(huán)時再從隊列中取出鸠真。
// 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;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> current = new ArrayList<>();
int length = queue.size();
for (int i=0; i<length; i++) {
Node curr = queue.poll();
current.add(curr.val);
for (Node n : curr.children) {
queue.offer(n);
}
}
result.add(current);
}
return result;
}
}
03 第二種解法
使用深度優(yōu)先算法（DFS）悯仙，此方法就需要使用遞歸來操作了。
在樹的每一級吠卷，都可以看做是當前問題的子問題锡垄，因此我們將數(shù)組、根節(jié)點祭隔、層級這三個要素作為遞歸的條件偎捎。在遞歸方法中，如果當前節(jié)點為null，直接return茴她；如果當前result的大小和層級相等，就往result新加一個list程奠，然后從result中取出當前層級對應的數(shù)組丈牢，先將當前節(jié)點值添加進去，然后for-each遍歷其children瞄沙，每一個children都符合當前問題的描述己沛，在此調(diào)用方法自身，但是第三個參數(shù)層級需要往上加1距境，因為進入了當前節(jié)點的下一層級申尼。
// 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<>();
levelOrder(root, result, 0);
return result;
}
public void levelOrder(Node root, List<List<Integer>> result, int level) {
if (root == null) {
return ;
}
if (result.size() == level) {
result.add(new ArrayList<>());
}
List<Integer> list = result.get(level);
list.add(root.val);
for (Node n : root.children) {
levelOrder(n, result, level+1);
}
}
}
04 小結(jié)
算法專題目前已連續(xù)日更超過兩個月，算法題文章92+篇垫桂，公眾號對話框回復【數(shù)據(jù)結(jié)構(gòu)與算法】师幕、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關鍵詞诬滩，獲取系列文章合集霹粥。
以上就是全部內(nèi)容，如果大家有什么好的解法思路疼鸟、建議或者其他問題后控，可以下方留言交流，點贊空镜、留言浩淘、轉(zhuǎn)發(fā)就是對我最大的回報和支持！
