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二叉树的层次遍历怎么实现
文章出自:http://scyanting.com/article/gscigp.html