[数据结构与算法]LeetCode 107. Binary Tree Level Order Traversal II - 二叉树系列题19

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range?[0, 2000].
• -1000 <= Node.val <= 1000

题目要求从底向上水平遍历，即把从叶节点最低的一层开始到根节点的顶层结束，按顺序把一层层的节点值放入一个二维数组中。

其实这题跟我们熟悉的从顶向下水平遍历差不多，只是结果的顺序相反而已。因此算法实现基本相同，有BFS和DFS（递归）两种解法。BFS解法在刷前面的题已经多次实现。本文简单总结一下递归解法。?

递归解法是使用前序遍历算法依次把每个节点放入结果的对应位置中去。结果是一个二维数组用于存放每一层节点值，在进入递归函数只要知道节点是处于哪一层就知道应该把节点值放入结果的什么位置，因此在前序遍历时应增加一个变量表示层数（根节点是第0层，随着递归深入层数变量加1），该层数变量就是对应结果数组的索引。由于事先并不知总层数，因此结果数组应该是动态增长的。

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        def helper(node, level):
            if not node:
                return
            nonlocal res
            if level == len(res):
                res.append([node.val])
            else:
                res[level].append(node.val)
            helper(node.left, level+1)
            helper(node.right, level+1)
        
        helper(root, 0)
        return res[::-1]