问题描述
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],
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
补充说明：
给定一个二叉树，遍历这个树，然后给出从下到上节点的值。
方案分析
- 又一个二叉树的操作，这道题目一看就让人想到了层次遍历。与层次遍历唯一的区别是从下到上遍历。
- 先实现层次遍历的从上到下遍历，翻转列表就达到目标了。
- 这里笔者提供的代码并未翻转列表，而是用到了deque，其实一样的道理。
- 层次遍历的核心原理：
- 先将根节点加入一个队列中
- 判断这个队列是否为空，如果不为空，则从队列左侧弹出一个节点，将这个节点的值加入结果列表中。
- 如果这个节点拥有左孩子，则将左孩子从右侧加入队列中，同理，如果这个节点拥有右孩子，则将右孩子加入队列中。
- 重复上面2-3步骤，直到队列中不存在元素。
- 得到的结果就是层次遍历的结果。
python实现
# 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]]
"""
if not root:
return []
from collections import deque
result = deque()
queue = deque([root])
while(queue):
level=[]
for i in range(len(queue)):
front=queue.popleft()
level.append(front.val)
if front.left:
queue.append(front.left)
if front.right:
queue.append(front.right)
result.appendleft(level)
return list(result)
方案分析2
- 看到这个问题，很容易想到二叉树搜索的两个基本算法——深度优先算法和广度优先算法。
python实现2
# 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):
# 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, res = collections.deque([(root, 0)]), []
while queue:
node, level = queue.popleft()
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
