028-力扣刷题107--二叉树的层次遍历-II

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

例如： 给定二叉树 [3,9,20,null,null,15,7],

image.png

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None: #如果root这个节点对象是空的就返回空的lieb
            return []
        result,current=[],[root] #result用于存储遍历的结果,我们从上到下进行遍历,最后输出的时候倒着输出就行,current中存储的是目前需要进行遍历的对象
        while current: #当current中有对象的时候我们就需要继续向下遍历
            next_levels,vals=[],[]  #next_levels存储的是下一层需要进行遍历的对象,vals就是遍历到的这一层的元素
            for node in current: #遍历这一层的节点对象:将他们的值进行存储
                vals.append(node.val)
                #从左到右存储要遍历的下一层的节点对象,这样取得时候也是从左到右存值
                if node.left:#如果这个节点有左孩子存储到临时存储这一层节点对象的列表中 
                    next_levels.append(node.left)
                if node.right:
                    next_levels.append(node.right)
            result.append(vals) #将这一层的元素值列表进行存储
            current=next_levels#更新current中存储的需要遍历的对象
        return result[::-1]#进行反转输出