LeetCode N叉树的层序遍历

题目

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

示例

  例如，给定一个 3叉树 :

解法

一、广度优先搜索( Python )

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root == None:
            return []
        n_stack = [root]
        res = []
        while n_stack:
            length = len(n_stack)
            level_list = []
            while length:
                tmp = n_stack.pop(0)
                level_list.append(tmp.val)
                n_stack.extend(tmp.children)
                length -= 1
            res.append(level_list)
        return res

基本思路

  在广度优先搜索的同时，将每一层的节点的值组成list，最后放到一个总的list里。

复杂度分析

  时间复杂度为$O\left(N\right)$。空间上用了一个栈来实现迭代，不考虑只有根节点的极端情况，满T叉树时栈的最大深度为倒数第二层的节点数量+T - 1，倒数第二层节点数量为$T^{k-2}$(k为总层数)，树的总节点数为$\frac{1-T^k}{1-T}$，两者相除，可以得出空间复杂度为$O\left(N\right)$。

优化

每次将首元素从列表里pop出来可能会有较大的开销，因此可以考虑另外一种迭代方式。

class Solution(object):
    def levelOrder(self, root):
        if not root:return []
        res = []
        stack = [root]
        while stack:
            temp = []
            next_stack = []
            for node in stack:
                temp.append(node.val)
                for child in node.children:
                    next_stack.append(child)
            stack = next_stack
            res.append(temp)
        return res

  这里的思路是将每一层的节点放入另外一个列表里next_stack，在该层所有节点都放进去之后，直接将next_stack赋值给stack，从而避免了pop操作。

  还有一种简洁版的，但是效率一般：

class Solution(object):
    def levelOrder(self, root):
        q, ret = [root], []
        while any(q):
            ret.append([node.val for node in q])
            q = [child for node in q for child in node.children]
        return ret