1、题目
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
输出：
[
[15,7],
[9,20],
[3]
]
2、解答
这道题和102题是差不多的，就是最后结果翻转一下就行了，所以还是之前的解法。
def levelOrderBottom(self, root):
"""
bfs:和102到题目一样，只是返回结果时倒序就行
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
res = []
queue = []
queue.append(root)
while len(queue) > 0:
size = len(queue)
level_list = []
while size > 0:
cur = queue.pop(0)
if cur.left is not None:
queue.append(cur.left)
if cur.right is not None:
queue.append(cur.right)
size -= 1
level_list.append(cur.val)
res.append(copy.deepcopy(level_list))
return res[::-1]
def levelOrderBottom2(self, root):
"""
dfs:和102到题目一样，只是返回结果时倒序就行
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
self.dfs(root, res, 0)
return res[::-1]
def dfs(self, node, res, level):
if node is None:
return
if len(res)<level+1:
res.append([])
if node.left is not None:
self.dfs(node.left, res, level+1)
if node.right is not None:
self.dfs(node.right, res, level+1)
res[level].append(node.val)
|