LeetCode 107. 二叉树的层序遍历 II

题目

给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

方法：递归

思路同 102. 二叉树的层序遍历

• result 存放层序遍历的结果

DFS 函数：

• 若节点为空节点，那么返回 None
• （因为记录结果的列表的记录方式为列表的不断嵌套，同一层的所有结点的值放在同一个列表中；同时，又因为我们将二叉树的深度从零开始，所以当进入一个新的深度时，此时记录结果的列表的长度是等于该层的深度的。）判断此时记录结果的列表长度是否等于此时需要遍历的层的深度，若相等，则表示此时为第一次遍历该层，所以在原始列表中嵌套新的列表
• 添加中间节点至此时深度的列表
• 若该中间节点存在左孩子，则使该左孩子作为新的中间节点开始新一轮递归
• 若该中间节点存在右孩子，则使该右孩子作为新的中间节点开始新一轮递归

• 调用 DFS 函数，开始遍历，并设其实深度为 0
• 因为此时 result 中存放的是自上向下的节点值，而题目要求的是自底向上的节点值，那么互换位置

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrderBottom(self, root):
        result = []

        def DFS(node, depth):
            if not node:
                return None
            if len(result) == depth:
                result.append([])
            result[depth].append(node.val) 
            if node.left:
                DFS(node.left, depth + 1)
            if node.right:
                DFS(node.right, depth + 1)

        DFS(root, 0)

        for i in range(len(result)/2):
            result[i], result[len(result)-i-1] = result[len(result)-i-1], result[i]

        return result