Type: Easy, BFS

問題描述：

Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
給定一個n叉樹，返回樹的層序遍歷的節(jié)點(diǎn)值，從左到右，從上到下。
For example, given a 3-ary tree:

img

We should return its level order traversal:

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

Note:

1. The depth of the tree is at most 1000.
2. The total number of nodes is at most 5000.

"""
# Definition for a Node.
# Childre是個Node引用數(shù)組，
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
        
"""
class Solution(object):
    # 層序遍歷需要知道知道如何確定一層
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        # 需要記錄層序，使用字典結(jié)構(gòu)
        que = [[root, 0]]
        record = {}
        layer = 1
        
        while elements != []:
            [cur, layer] = elements.pop(0)
            
            if cur != None:
                if layer not in record: # 根據(jù)鍵判斷
                    record[layer] = [cur.val]
                else:
                    record[layer] += [cur.val]
                    
                for child in cur.children:
                    elements += [[child, layer + 1]]
                
        res = [[None]] * len(record)
        for key, val in record.items():
            res[key - 1] = val
            
        return res

"""
# Definition for a Node.
# Childre是個Node引用數(shù)組，
class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children
        
"""
class Solution(object):
    # 層序遍歷需要知道知道如何確定一層
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        # 需要記錄層序，使用字典結(jié)構(gòu)
        que = [[root, 0]]
        record = {}
        layer = 0
        
        while que != []:
            [cur,layer] = que.pop(0)
            if cur != None:
                if layer not in record:
                    record[layer] = [cur.val]
                else:
                    record[layer] += [cur.val]
                for child in cur.children:
                    que += [[child, layer + 1]]
        res = [[None]] * len(record) # [[None],[None],[None],...] 
        for key, val in record.items():
            res[key] = val # val是個數(shù)組
        return res
        

和前面的算法基本一致，這里再拆解一下，簡單說，就是用字典來記錄樹的層的數(shù)據(jù)，用先進(jìn)先出的隊(duì)列來進(jìn)行遍歷。
從根部開始，先加入隊(duì)列，注意，這里的隊(duì)列是用數(shù)組來模擬的，Python的數(shù)組有pop方法，非常好用。

因?yàn)槭菍有蜉敵?，所以跟蹤層的序號，在將?jié)點(diǎn)加入到隊(duì)列時，節(jié)點(diǎn)的層序也放進(jìn)來。

一個非常容易犯錯的點(diǎn)是，在將已經(jīng)pop出去的節(jié)點(diǎn)的孩子加入隊(duì)列時，二叉樹就是加入左右即可，n叉樹需要用一個for循環(huán)。注意一定加入的是當(dāng)前pop出去的孩子節(jié)點(diǎn)，是cur.children不是root.children，這個錯非常容易犯。

最后，用數(shù)組來拿出字典的數(shù)值，最后的res = [[None]] * len(record)值得好好看看，并活用。
END.