###### tags: `Leetcode` `medium` `tree` `bfs` `python`

# 429. N-ary Tree Level Order Traversal

## [題目連結:]https://leetcode.com/problems/n-ary-tree-level-order-traversal/

## 題目:
Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).



Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

#### [圖片來源:]https://leetcode.com/problems/n-ary-tree-level-order-traversal/

## 解題想法:
* 題目要求每一層裝在同一個list中
* 給的Node(val,children):
* val: int
* children: list
* example1示意圖
* 

* BFS遍歷每一層
* 若有child，則將child list的所有node逐一取出加入下一層

## Python (BFS):

# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
    def printNode(self):
        root=self
        que=[root]
        res=[]
        while que:
            cur=que.pop(0)
            res.append(cur.val)
            if cur.children:
                for val in cur.children:
                    que.append(val)
        print(res)

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Node
        :rtype: List[List[int]]
        """
        if not root:
            return []
        que=[root]
        res=[]
        while que:
            nextLevel=[] #裝下一層
            tmp=[] #裝當前node
            for node in que:
                tmp.append(node.val)
                if node.children:
                    for child in node.children:
                        nextLevel.append(child)
            res.append(tmp)
            que=nextLevel
        return res

if __name__ == '__main__':

    Level1=[Node(1)]
    Level2=[Node(3),Node(2),Node(4)]
    Level3=[Node(5),Node(6)]
    #Level Structure
    Level1[0].children=Level2
    Level2[0].children=Level3
    #show N-ary
    Level1[0].printNode()
    #[1, 3, 2, 4, 5, 6]

    result=Solution()
    ans=result.levelOrder(Level1[0])
    print(ans)
    #[[1], [3, 2, 4], [5, 6]]