搜索与回溯算法——层次遍历二叉树
2021/9/30 20:12:30
本文主要是介绍搜索与回溯算法——层次遍历二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer 32 - I. 从上到下打印二叉树
层次遍历,用到队列(先进先出).
queue.Queue()
collections.deque()
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None from queue import Queue # queue 不是大写 class Solution: def levelOrder(self, root: TreeNode) -> List[int]: node = [] if root is None: return node # 当输入为[] q = Queue() q.put(root) while not q.empty(): out = q.get() node.append(out.val) if out.left is not None: # is not 不是 not q.put(out.left) if out.right is not None: q.put(out.right) return node
双端队列
class Solution: def levelOrder(self, root: TreeNode) -> List[int]: if not root: return [] res, queue = [], collections.deque() queue.append(root) while queue: node = queue.popleft() res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res
剑指 Offer 32 - II. 从上到下打印二叉树 II
层次遍历,但要找到每一层最后一个节点
deque操作
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None from queue import Queue from collections import deque class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] node = [] sub = [] last_node = root q = deque() q.append(root) while q: # 判断不为空 out = q.popleft() # 左侧出来 sub.append(out.val) if out.left is not None: # is not 不是 not q.append(out.left) if out.right is not None: q.append(out.right) if out==last_node: node.append(sub) sub = [] if q: # 如果没有下一层了 last_node = q.pop() # 右侧出来 q.append(last_node) # 右侧进去 return node
循环一层里面的节点,在循环下一层,因为读取第t层,不会含有t+2层
class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] res, queue = [], collections.deque() queue.append(root) while queue: tmp = [] for _ in range(len(queue)): node = queue.popleft() tmp.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(tmp) return res
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
只能在加入到列表的时候操作,因为存储的队列要按照二叉树的结构。右边读取队列节点时,总时读最后一个,就不是二叉树结构了。
最后只需要加一个变量记录是奇数还是偶数,然后在sub列表中,左边加入或者右边加入。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] node = [] sub = deque() # 列表变为双端队列 last_node = root q = deque() q.append(root) layer = 1 while q: # 判断不为空 out = q.popleft() # 左侧出来 if layer % 2: sub.append(out.val) else: sub.appendleft(out.val) if out.left is not None: # is not 不是 not q.append(out.left) if out.right is not None: q.append(out.right) if out==last_node: layer += 1 node.append(list(sub)) # 把队列换成list 注意可以转换的 sub = deque() if q: # 如果没有下一层了 last_node = q.pop() # 右侧出来 q.append(last_node) # 右侧进去 return node
这篇关于搜索与回溯算法——层次遍历二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南