当前位置:网站首页>二叉树 | 迭代遍历 | leecode刷题笔记
二叉树 | 迭代遍历 | leecode刷题笔记
2022-08-10 22:23:00 【Begonia_cat】
文章目录
跟随carl代码随想录刷题
语言:python
二叉树的迭代遍历——深度优先
统一迭代法推荐
将要访问的节点
放入栈中,把要处理的节点
也放入栈中但是要做标记
(要处理的节点放入栈之后,紧接着放入一个空指针做标记
)。
前序遍历、中序遍历、后序遍历迭代法代码的唯一区别就是下面三个子句的顺序
:
if node.right: st.append(node.right)
# 右节点进栈if node.left: st.append(node.left)
# 左节点进栈st.append(node)
st.append(None)
# 中节点进栈- 把握一个原则:进栈顺序与出栈顺序相反
- 前序遍历期望的出栈顺序是
中 左 右
,所以进栈顺序是右 左 中
- 中序遍历期望的出栈顺序是
左 中 右
,所以进栈顺序是右 中 左
- 后序遍历期望的出栈顺序是
左 右 中
,所以进栈顺序是中 右 左
思路分析——以中序遍历为例
思路分析——以中序遍历为例(中序遍历的顺序是:左中右
)
- 首先将
根节点
压入栈中,作为开始遍历的起点 - 遍历开始
- 只要
当前节点
不为空,就弹出当前节点
,对当前节点
进行下一步检查(压栈顺序右中左
与出栈顺序相反):如果
当前节点的右节点存在,就压入栈中- 把
当前节点
压入栈中,再压入一个空节点
️这一步是一定会执行的 如果
根节点的左节点存在,就压入栈中
- 只要
经过一次遍历操作之后,我们会得到以下两种情况的栈内容:
当前节点
的左节点
存在:st = [……, 中, None,左
]- 此时需要进一步遍历
左
节点的右左子树,再次进行上述迭代
- 此时需要进一步遍历
当前节点
的左节点不存在:st = [……, 中, None]- 说明
当前节点
已到达最底部,不用再遍历,可以直接存入结果集。 - 而
None
就是作为是否可以存入结果集的标记:如果弹出为None
,就继续再弹出一个,并将其存入结果集。
- 说明
举个例子吧:
94. 二叉树的中序遍历——迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
st = []
if root:
st.append(root) # 根节点压入栈
while st:
node = st.pop() # node等于根节点
if node != None:
if node.right: # 如果右节点存在,就压入栈
st.append(node.right)
""" 1. 中节点压入栈 2. 再压入一个空节点 因为中节点访问过,但是还没有处理,加入空节点作为标记 """
st.append(node)
st.append(None)
if node.left: # 如果左节点存在,则压入栈
st.append(node.left)
else: # 只有遇到空节点的时候,才将下一个节点放入结果集
node = st.pop() # 重新取出栈中元素
result.append(node.val) # 存入结果集
return result
144. 二叉树的前序遍历——迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
st.append(node)
st.append(None)
else:
node = st.pop()
result.append(node.val)
return result
145. 二叉树的后序遍历——迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
st.append(node)
st.append(None)
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result
附:另一种写法emm……看一下就行
前序遍历(迭代法)
先将根节点放入栈中,然后将
右孩子
加入栈,再加入左孩子
,这样,出栈的时候就是中左右
的顺序。注意:根节点最开始就出栈定义共分两部分:
- 处理:将元素放进
result
数组中 - 访问:遍历节点
- 处理:将元素放进
因为前序遍历要访问
和处理
的元素都是中间节点
,所以代码写起来简单。
完整代码如下(不推荐)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# 根节点为空则返回空列表
if not root:
return []
stack = [root] # 否则,先将根节点压入栈中
result = [] # 初始化一个空列表用于存放结果集
while stack:
node = stack.pop() #
# 中节点先处理
result.append(node.val) # 结果集中存入中节点的值
# 右孩子先入栈
if node.right: # 如果当前节点的右孩子存在,就入栈
stack.append(node.right)
# 左孩子后入栈
if node.left: # 如果当前节点的左孩子存在,就入栈
stack.append(node.left)
return result
BUT!!! 中序遍历
和后序遍历
没有办法在前序遍历
的基础上进行调整,而是需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
。好麻烦
边栏推荐
猜你喜欢
字节跳动原来这么容易就能进去...
August 10, 2022: Building Web Applications for Beginners with ASP.NET Core -- Creating Web UIs with ASP.NET Core
“数据引擎”开启前装规模量产新赛道,「智协慧同」崭露头角
What is Jmeter? What are the principle steps used by Jmeter?
实例054:位取反、位移动
阿里云新增三大高性能计算解决方案,助力生命科学行业快速发展
Distribution Network Expansion Planning: Consider Decisions Using Probabilistic Energy Production and Consumption Profiles (Matlab Code Implementation)
68:第六章:开发文章服务:1:内容梳理;article表介绍;创建【article】文章服务;
Power system power flow calculation (Newton-Raphson method, Gauss-Seidel method, fast decoupling method) (Matlab code implementation)
CFdiv2-Beautiful Mirrors-(期望)
随机推荐
Nodes in the linked list are flipped in groups of k
自学软件测试不知道该如何学起,【软件测试技能图谱|自学测试路线图】
leetcode:357. 统计各位数字都不同的数字个数
【软件测试】2022年最火的十大测试工具,你掌握了几个
Addition of linked lists (2)
CIKM2022 | 基于双向Transformers对比学习的序列推荐
2022年8月的10篇论文推荐
12 Recurrent Neural Network RNN2 of Deep Learning
Distribution Network Expansion Planning: Consider Decisions Using Probabilistic Energy Production and Consumption Profiles (Matlab Code Implementation)
Detailed installation steps and environment configuration of geemap
68:第六章:开发文章服务:1:内容梳理;article表介绍;创建【article】文章服务;
CFdiv2-Beautiful Mirrors-(期望)
make & cmake
实例049:lambda
August 10, 2022: Building Web Applications for Beginners with ASP.NET Core -- Creating Web UIs with ASP.NET Core
链表中的节点每k个一组翻转
How to be a Righteous Hacker?What should you study?
shell脚本
An article to teach you a quick start and basic explanation of Pytest, be sure to read
阿里云架构师金云龙:基于云XR平台的视觉计算应用部署