429. N叉树的层序遍历

2019/7/24 11:34:30 人评论 次浏览 分类:学习教程

题目

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

例如,给定一个 3叉树 :
返回其层序遍历:

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

分析

此题有两种解法:
第一种仍然是像遍历二叉树一样遍历,但是要注意的是,这里是N叉树,所以需要两个队列.
第二种则是使用递归方式,效率更高一下

代码

解法1:

 /**
     * 土鳖做法:用父子队列来做,效率很低
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<Node> parentQueue = new LinkedList<>();
        Queue<Node> sonQueue = new LinkedList<>();
        parentQueue.offer(root);

        int index = 0;
        while (!parentQueue.isEmpty()) {
            Node cur = parentQueue.poll();

            while(result.size()<index+1){
                result.add(new ArrayList<Integer>());
            }
            result.get(index);
            List<Node> childrens = cur.children;
            for (Node children : childrens) {
                sonQueue.offer(children);
            }
            if (parentQueue.isEmpty()) {
                if (!sonQueue.isEmpty()) {
                    parentQueue = null;
                    parentQueue = sonQueue;
                    sonQueue = new LinkedList<>();
                    index++;
                }
            }
        }
        return result;
    }

解法2:

    /**
     * 递归方式
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder2(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        levelOrder(root,0,result);
        return result;
    }


    private void levelOrder(Node node,int depth,List<List<Integer>> result){
        if(node == null){
            return;
        }

        if(depth+1>result.size()){
            result.add(new ArrayList<>());
        }
        result.get(depth).add(node.val);


        for (Node child : node.children) {
            levelOrder(child,depth+1,result);
        }
    }

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->