【python实现】leetcode107. 二叉树的层次遍历 II

Python publisher01 24℃ 0评论

简介:

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

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为:

[
  [15,7],
  [9,20],
  [3]
]

解题思路:

看到这道题,首先想到用BFS广度优先搜索,可以使用数据结构queue队列来实现广度优先搜索,
每入队一层,记录这一层队列的个数,在遍历每个节点的时候,将每个节点的左右节点加入队列,同时这个节点出队,
这样接保证了可以分层打印节点,这样就是从上到下按层遍历二叉树,如果想倒序打印,就把记录下来的值,翻转一下数组。

python答案:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        
        if root == None:
            return []
        queue = [root]
        result = []
        
        while queue:
            tmplist = []
            //记录队列节点个数
            length = len(queue)
            //遍历队列
            for i in range(length):
                //节点出队
                tmp = queue.pop(0)
                //记录节点
                tmplist.append(tmp.val)
                //左右节点入队
                if tmp.left != None:
                    queue.append(tmp.left)
                if tmp.right != None:
                    queue.append(tmp.right)
            result.append(tmplist)
        
        //翻转输出结果
        return result[::-1]
        
             

你或许想:《去原作者写文章的地方

转载请注明:Python量化投资 » 【python实现】leetcode107. 二叉树的层次遍历 II

喜欢 (0)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址