import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Deque;

import java.util.List;

public class LevelOrder_429 {

class Node {

public int val;

public List<Node> children;

public Node() {}

public Node(int _val) {

val = _val;

}

public Node(int _val, List<Node> _children) {

val = _val;

children = _children;

}

}

/**

* 递归解法：一般不通过递归算法来进行层序遍历即广度优先搜索。因为广度优先搜索基于队列，而递归运行时使用堆栈适用于深度优先搜索

* @param root

* @return

*/

// 1. 关于树的递归，递归的界限往往以树为单位，即一次递归的处理范围包括传入的根节点及它的孩子节点

private List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> levelOrder1(Node root) {

if (root != null) traverseNode(root, 0);

return res;

}

private void traverseNode(Node node, int level) {

// 如果返回结果列表当前大小等于level，则增加一个list存放下一层的遍历结果

if (res.size() == level) {

res.add(new ArrayList<>());

}

// 在当前层列表中加入传入节点的值

res.get(level).add(node.val);

// 遍历子节点执行递归逻辑

for (Node childNode : node.children) {

traverseNode(childNode, level + 1);

}

}

/**

* 使用队列进行广度优先遍历

* @param root

* @return

*/

public List<List<Integer>> levelOrder2(Node root) {

List<List<Integer>> res = new ArrayList<>();

if (root == null) {

return res;

}

Deque<Node> queue = new ArrayDeque<>();

// 把当前节点添加到队列

queue.add(root);

while(!queue.isEmpty()) {

List<Integer> resPerLevel = new ArrayList<>();

int size = queue.size();

for (int i = 0; i < size; i++) {

// 每层的节点依次出队

Node node = queue.remove();

// 每层的遍历结果添加至容器

resPerLevel.add(node.val);

// 出队的节点将其子节点依次入队

queue.addAll(node.children);

}

res.add(resPerLevel);

}

return res;

}

}