Python二叉树的层次遍历怎么实现

这篇文章主要介绍“Python二叉树的层次遍历怎么实现”，在日常操作中，相信很多人在Python二叉树的层次遍历怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Python二叉树的层次遍历怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

创新互联公司是一家专注于网站制作、网站建设与策划设计,长安网站建设哪家好?创新互联公司做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:长安等地区。长安做网站价格咨询:18982081108

题目

---

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

例如：

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

    3
   / \
  9  20
    /  \
   15   7

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

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

解题思路

---

思路：广度优先搜索（BFS）

先看题目，题目要求返回节点值自底向上的层次遍历。（从叶子节点所在层往根节点所在层，逐层从左到右遍历）。

那么我们可以发现，使用广度优先搜索的方法是最直观的，题目要求自底向上，这里我从上到下遍历搜索时先用栈存储，然后再实现逆序（即自底向上）。具体的做法如下：

• 从根节点开始搜索；

• 每次搜索的时候先确定当前层的节点数量，遍历当前层的全部节点，用列表存储当前层的节点值；

• 用栈存储上述存储每层节点值的列表，后续实现逆序。

具体代码实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        ans = []

        stack = []

        queue = deque()
        queue.append(root)

        while queue:
            cnt = len(queue)
            
            tmp = []

            for _ in range(cnt):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                tmp.append(node.val)
            
            stack.append(tmp)
        
        while stack:
            ans.append(stack.pop())
        
        return ans

到此，关于“Python二叉树的层次遍历怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！

文章名称：Python二叉树的层次遍历怎么实现
文章URL：https://www.cdcxhl.com/article18/gscigp.html

成都网站建设公司_创新互联，为您提供虚拟主机、网站制作、网站内链、品牌网站设计、网站收录、域名注册

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联