107.二叉树的层次遍历 ii
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
解法1 递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
result = []
self.recur(root, 1, result)
return result
def recur(self, node, layer, result):
if not node:
return
# 判断当前节点的层数 是否大于 result中的列表数
if layer > len(result):
# 若是 则在result的前部增加一个列表
result.insert(0, [])
# 将该节点的值添加到result中对应的列表
result[-layer].append(node.val)
# 递归
self.recur(node.left, layer + 1, result)
self.recur(node.right, layer + 1, result)
解法2 迭代
self
队列
队列中每个元素为一个元组,包括节点和节点所在层数
字典
key 是层数 value 是列表 元素为每个节点的值
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
l = [(root, 1)]
d = {}
while l:
node, layer = l.pop(0)
if d.__contains__(layer):
d[layer].append(node.val)
else:
d[layer] = [node.val]
if node.left:
l.append((node.left, layer + 1))
if node.right:
l.append((node.right, layer + 1))
result = []
layers = sorted(d.keys())
while layers:
layer = layers.pop()
result.append(d[layer])
return result
优化
在每次进入循环后,弹出这一层的所有节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
l = [root]
result = []
while l:
temp = []
n = len(l)
for i in range(n):
node = l.pop(0)
temp.append(node.val)
if node.left:
l.append(node.left)
if node.right:
l.append(node.right)
result.insert(0, temp)
return result