# Binary Tree Level Order Traversal

###### tags: `Easy`、`Tree`



## 非遞迴解
- 找出每一層的節點即可

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
         output = []
         curr_level = []    
         level = 0
         q = deque()
         q.append([root, level])
         while q:
             node, node_level = q.popleft()
             if node.left:
                 q.append([node.left, node_level+1])
             if node.right:
                 q.append([node.right, node_level+1])            
             if level != node_level:
                 output.append(curr_level)
                 curr_level = []
                 level += 1
             curr_level.append(node.val)
         if curr_level: output.append(curr_level)            
         return output 

## 遞迴解

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return root
           
        # DFS? recursive
        ans = []
        def traversal(level, node): 
            # function not returning anything but just modifying output
            if node:
                if len(ans) <= level:
                    ans.append([node.val])
                else:
                    ans[level].append(node.val)
                traversal(level+1, node.left)
                traversal(level+1, node.right)
                
        traversal(0, root)
        
        return ans