leetcode N叉树的层序遍历

Yunxiao 2020年07月16日 475次浏览

题目描述

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

例如,给定一个 3叉树 :

image.png
返回其层序遍历:

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

分析

题目难点主要就在如何把节点一层层的分开。我想到的是用一个temp列表来记录“当前层节点”

然后依次展开当前层节点的所有子节点到一个tempChildren列表中。

顺便把所有当前层节点的值也记录到一个list中。当temp中节点展开完后,也就是temp为空时,则表示当前层所有节点已经遍历完成

此时(temp为空时),把list加入结果中,把tempChildren的值赋给temp.然后回到最开始。直到tempChildren最后为空。也就遍历完成了

代码如下:

/*
// Definition for a Node.
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;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans =new LinkedList();
        LinkedList<Node> temp= new LinkedList();
        LinkedList<Node> tempChildren= new LinkedList();
        List<Integer> list = new LinkedList();
        if(root==null) return ans;
        temp.add(root);
        while(!temp.isEmpty()){
            Node node=temp.pollFirst();
            list.add(node.val);

            if(node.children!=null){
                for(Node children : node.children){
                    tempChildren.add(children);
                }
            }

            if(temp.isEmpty()){

                ans.add(new LinkedList<>(list));
                list.clear();
                for (Node nodechildren:tempChildren
                     ) {
                    temp.add(nodechildren);
                }
                tempChildren.clear();
            }
        }
        return ans;
        
    }
}

问题--浅拷贝和深拷贝

这个思路是没问题的,可最开始出来的结果总是为空。打断点调试才发现是深浅拷贝的问题

我们来看这段代码

ans.add(new LinkedList<>(list));
list.clear();
for (Node nodechildren:tempChildren
    ) {
    temp.add(nodechildren);
}
tempChildren.clear();

本来我是这样写的

ans.add(list);
list.clear();
temp=tempChildren;
tempChildren.clear();

然后就出现了上述问题,比如本来向ans中添加的list是正常有值的,但是执行list.clear()这个方法后,ans中已经添加的list也会被清空,这是因为在内存中俩个list指向的一块内存。下面的temp和tempChildren同理。所有就改成了第一版代码(ps.网上实现深拷贝的方法感觉都比较复杂,这里的需求也比较简单,就直接new了)

更加优雅的方案

力扣给的官解第一种方法和我的很类似,只是它没有使用tempChildren这个列表。而是把temp变成了队列,然后使用for循环来控制每一层。这里使用队列是有一定好处的,能大幅减低时间复杂度

使用队列十分重要,如果使用 Vector,List,Array 的话,我们删除元素需要 O(n)的时间复杂度。而队列删除元素只需要 O(1)的时间。

下面是具体代码

// This code is a modified version of the code posted by
// #zzzliu on the discussion forums.
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> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                queue.addAll(node.children);
            }
            result.add(level);
        }
        return result;
    }
}

这个For循环时很精妙的,其他的和我的代码大差不差。具体解释下这个for循环。

在For循环之前,它先得到了当前队列的长度,这样就可以控制for循环只循环“当前层”。而在for循环内部,又依次删除了“当前层”的所有元素,并把“当前层”的所有子节点展开到队列中,同时记录了当前层的的元素值到level这个列表中。同时注意它这个level列表的定义位置在while内部,也就避免了我上面代码的"浅拷贝"清空的问题。相对来说优雅了很多

其他方案

此外,力扣还给了另外一种方法,简化的广度搜索

// This code is a modified version of the code posted by
// #zzzliu on the discussion forums.
class Solution {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        List<Node> previousLayer = Arrays.asList(root);

        while (!previousLayer.isEmpty()) {
            List<Node> currentLayer = new ArrayList<>();
            List<Integer> previousVals = new ArrayList<>();
            for (Node node : previousLayer) {
                previousVals.add(node.val);
                currentLayer.addAll(node.children);
            }
            result.add(previousVals);
            previousLayer = currentLayer;
        }

        return result;
    }
}


其实我感觉也差不多时一种方法...