Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
Example:
Given binary tree [3,9,20,null,null,15,7],
1
2
3
4
5
| 3
/ \
9 20
/ \
15 7
|
return its level order traversal as:
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
Solution
(Binary-Tree-Level-Order-Traversal.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| # 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]]
"""
stack = []
ret = []
if not root:
return ret
stack.append(root)
while stack:
new_stack = []
ret.append([x.val for x in stack])
for node in stack:
if node.left:
new_stack.append(node.left)
if node.right:
new_stack.append(node.right)
stack = new_stack
return ret
|