描述
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
分析
Level Order Traveral的姐妹版，要求最底层的先输出。
代码
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
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
queue = deque()
d = {}
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 [v for k, v in sorted(d.items(), key=lambda x: -x[0])]
|