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);
        }
    }

相关资讯

    暂无相关的资讯...

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

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