LeetCode 107. Binary Tree Level Order Traversal II

题目

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,null,null,15,7],

1
2
3
4
5
3
/ \
9 20
/ \
15 7

return its bottom-up level order traversal as:

1
2
3
4
5
[
[15,7],
[9,20],
[3]
]

分析

二叉树的从底向上顺序/层次遍历

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# 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 levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# dfs recursively
def levelOrderBottom1(self, root):
res = []
self.dfs(root, 0, res)
return res
def dfs(self, root, level, res):
if root:
if len(res) < level + 1:
res.insert(0, [])
res[-(level+1)].append(root.val)
self.dfs(root.left, level+1, res)
self.dfs(root.right, level+1, res)
# dfs + stack
def levelOrderBottom2(self, root):
stack = [(root, 0)]
res = []
while stack:
node, level = stack.pop()
if node:
if len(res) < level+1:
res.insert(0, [])
res[-(level+1)].append(node.val)
stack.append((node.right, level+1))
stack.append((node.left, level+1))
return res
# bfs + queue
def levelOrderBottom(self, root):
queue = [(root, 0)]
res = []
while queue:
node, level = queue.pop(0)
if node:
if len(res) < level+1:
res.insert(0, [])
res[-(level+1)].append(node.val)
queue.append((node.left, level+1))
queue.append((node.right, level+1))
return res

点评

递归版本的深度优先搜索算法里,要注意 dfs 的功能!每次递归的时候,传递了子树根节点,层次,还有最后的结果数组,如果 res 的大小比深度小,还要在 res 里新建一个层,然后对左右子树分别 dfs
迭代的栈版本和队列版本基本一致,这里和之前的不同,主要是每次迭代时还传递了层次信息