N叉树的层序遍历

题目

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个3叉树:

image

返回其层序遍历:

[
     [1],
     [3,2,4],
     [5,6]
]

说明:

树的深度不会超过1000。
树的节点总数不会超过5000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

对于树的处理,一般分为递归和迭代两种.

• 递归
  • 递归处理中直接对List<Node>处理比较苦难,可以转换为对同一层级的node做处理,因此需要控制层级
• 迭代
  • 迭代的思路在于要使用一种数据结构将原有树转化为平层的结构.此处我们使用队列来解决,这样可以保证是从左到右,先进先出.

代码

递归的代码

/*
// 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;
        }
        doRecursion(result,0,root);
        return result;
    }
    
    private void doRecursion(List<List<Integer>> result,int level,Node node){
        if(node == null){
            return;
        }
        if(result.size() < level+1){
            result.add(new ArrayList());
        }
        result.get(level).add(node.val);
        if(node.children != null){
            for(Node cNode:node.children){
                doRecursion(result,level+1,cNode);
            }
        }
    }
}

迭代的代码

/*
// 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();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList();
            int count = queue.size();
            while(count > 0){
                Node node = queue.poll();
                list.add(node.val);
                if(node.children != null){
                    for(Node child:node.children){
                        queue.add(child);
                    }
                }
                count--;
            }
            result.add(list);
        }
        return result;
    }
}