6/19/2017 - 9:45 AM

## 102. Binary Tree Level Order Traversal

1. Binary Tree Level Order Traversal
``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
queue = [root]
res = []
curLevel = []
rightmost = root
while len(queue) != 0:
curNode = queue[0]
del queue[0]
curLevel.append(curNode.val)
if curNode.left:
queue.append(curNode.left)
if curNode.right:
queue.append(curNode.right)
if curNode == rightmost:
res.append(curLevel)
if len(queue) != 0:
rightmost = queue[-1]
curLevel = []
return res``````
``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
queue = [root]
res = []
while len(queue) != 0:
curLevel = []
for i in range(len(queue)):
node = queue[0]
del queue[0]
curLevel.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(curLevel)
return res``````

https://leetcode.com/problems/binary-tree-level-order-traversal/#/description

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree `[3,9,20,null,null,15,7]`,

``````    3
/ \
9  20
/  \
15   7
``````

return its level order traversal as:

``````[
[3],
[9,20],
[15,7]
]
``````