LeetCode: 107. Binary Tree Level Order Traversal II

题目

原题地址：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

Comments