107. 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]
]

解法

层序遍历

层序遍历，将每层的结果保存到列表，最后反转列表。

class Solution():
    def levelOrderBottom(self, root):
        q, res = [root], []

        # any here is important,
        # or case such as [3] will fail.
        while any(q):
            res.append([node.val for node in q])
            q = [child for node in q for child in [node.left, node.right] if child]

        return res[::-1]

举个例子：

    3
   / \
  9  20
    /  \
   15   7

1   q[3]        res[3]                      q[9, 20]
2   q[9, 29]    res[3, [9, 20]]             q[15, 7]
3   q[15, 7]    res[3, [9, 20], [15, 7]]    q[]

递归解法

TODO: 深度优先、广度优先

any 的用法

In [1]: ?any
Signature: any(iterable, /)
Docstring:
Return True if bool(x) is True for any x in the iterable.

If the iterable is empty, return False.
Type:      builtin_function_or_method

In [2]: any([[]])
Out[2]: False

In [3]: bool([[]])
Out[3]: True

如果测试用例为 []，那么：

root = []
q = [root] = [[]]
while q:  # notiece this True
    # but node is [], has no val attribute.
    # so an `AttributeError: 'list' object has no attribute 'val'` will raise
    res.append([node.val for node in q])
    ...

while any(q):  # no such problem
    # any([[]]) -> bool([]) -> False
    # so will not reach here
    ...

所以此处必须使用 any。