###### tags: `Leetcode` `medium` `tree` `bfs` `python` `Top 100 Liked Questions`

# 102. Binary Tree Level Order Traversal

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

## 題目:
Given the ```root``` of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).


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

## 解題想法:
兄弟題目:
[103. Binary Tree Zigzag Level Order Traversal](/SBnNtwxETz23kMkyRp-a_Q)
[107. Binary Tree Level Order Traversal II](/snXH3IbERPiC3Y1N7M4_vA)
* 題目為給二元樹，求其level-order遍歷
* 使用bfs，每層進行遍歷
* Interactive
* Recursive
## Python: Interactive
* 每次紀錄當前的所有node.val與下層的node
* while繼續下一層

from collections import defaultdict
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res=[]
        que=[root]
        while que:
            curLevel=[] #紀錄當前node.val
            nextLevel=[] #紀錄下一層root
            for root in que:
                curLevel.append(root.val)
                if root.left:
                    nextLevel.append(root.left)
                if root.right:
                    nextLevel.append(root.right)
            res.append(curLevel)
            que=nextLevel #更新為下一層
        return res

root=TreeNode(3)
root.insertLeft(9)
root.insertRight(20)
root.right.insertLeft(15)
root.right.insertRight(7)
root.printTree()

result = Solution()
ans = result.levelOrder(root)
print(ans)

''' 
#也可以用dic存
class Solution(object):
    def levelOrder(self,root):
        if not root:
            return []
        
        ans = defaultdict(list)
        map = [ {'level':0, 'node':root} ]

        while map:
            cur = map.pop(0)
            root = cur['node']
            #將值存到對應層
            ans[cur['level']].append(root.val)
            #左子:
            if root.left:
                map.append({'level':cur['level']+1, 'node':root.left})
            if root.right:
                map.append({'level':cur['level']+1, 'node':root.right})
            
        return [ans[i] for i in ans]
'''

## Python: Recursive
* 使用字典存每層的node
* key=level
* val=list()

from collections import defaultdict
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        #bfs recursive
        self.res=defaultdict(list)
        self.bfs(root,1)
        return [ self.res[key] for key in self.res]
    def bfs(self,root,level):
        if not root:
            return 
        self.res[level].append(root.val)
        self.bfs(root.left,level+1)
        self.bfs(root.right,level+1)

root=TreeNode(3)
root.insertLeft(9)
root.insertRight(20)
root.right.insertLeft(15)
root.right.insertRight(7)
root.printTree()

result = Solution()
ans = result.levelOrder(root)
print(ans)