10
LeetCode: 107. Binary Tree Level Order Traversal II
source link: https://mozillazg.com/2021/01/leetcode-107-binary-tree-level-order-traversal-ii.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目¶
原题地址：https://leetcode.com/problems/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],
3 / \ 9 20 / \ 15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
解法¶
广度优先，从上到下一层一层遍历，保存每一层的 value，然后翻转保存的 value 数组。
这个方法的 Python 代码类似下面这样:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
up_to_buttom_values = self._level_order_up(root)
up_to_buttom_values.reverse()
return up_to_buttom_values
def _level_order_up(self, root):
if root is None:
return []
all_values = []
next_level_nodes = [root]
while next_level_nodes:
nodes = next_level_nodes
values = []
next_level_nodes = []
for node in nodes:
values.append(node.val)
if node.left is not None:
next_level_nodes.append(node.left)
if node.right is not None:
next_level_nodes.append(node.right)
if values:
all_values.append(values)
return all_values
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK