描述
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,#,#,15,7},
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
分析
广度优先遍历,用队列实现。
代码
Python
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
|
from collections import deque, OrderedDict
class (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]] """ queue = deque() d = OrderedDict() if not root: return [] queue.append((root, 0)) while queue: cur, idx = queue.popleft() d.setdefault(idx, []).append(cur.val) if cur.left: queue.append((cur.left, idx + 1)) if cur.right: queue.append((cur.right, idx + 1)) return d.values()
|
近期评论