0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

如何将前中后序的递归框架改写成迭代形式

算法与数据结构 来源:labuladong 作者:labuladong 2022-03-18 10:13 次阅读

之前经常讲涉及递归的算法题,我说过写递归算法的一个技巧就是不要试图跳进递归细节,而是从递归框架上思考,从函数定义去理解递归函数到底该怎么实现。

而且我们前文学习数据结构和算法的框架思维特别强调过,练习递归的框架思维最好方式就是从二叉树相关题目开始刷,前文也有好几篇手把手带你刷二叉树和二叉搜索树的文章:

之前的文章全部都是运用二叉树的递归框架,帮你透过现象看本质,明白二叉树的各种题目本质都是前中后序遍历衍生出来的。

前文BFS 算法框架详解是利用队列迭代地遍历二叉树,不过使用的是层级遍历,没有递归遍历中的前中后序之分。

由于现在面试越来越卷,很多读者在后台问我如何将前中后序的递归框架改写成迭代形式。

首先我想说,递归改迭代从实用性的角度讲是没什么意义的,明明可以写递归解法,为什么非要改成迭代的方式?

对于二叉树来说,递归解法是最容易理解的,非要让你改成迭代,顶多是考察你对递归和栈的理解程度,架不住大家问,那就总结一下吧。

我以前见过一些迭代实现二叉树前中后序遍历的代码模板,比较短小,容易记,但通用性较差。

通用性较差的意思是说,模板只是针对「用迭代的方式返回二叉树前/中/后序的遍历结果」这个问题,函数签名类似这样,返回一个TreeNode列表:

Listtraverse(TreeNoderoot);

如果给一些稍微复杂的二叉树问题,比如最近公共祖先二叉搜索子树的最大键值和,想把这些递归解法改成迭代,就无能为力了。

而我想要的是一个万能的模板,可以把一切二叉树递归算法都改成迭代

换句话说,类似二叉树的递归框架:

voidtraverse(TreeNoderoot){
if(root==null)return;
/*前序遍历代码位置*/
traverse(root.left);
/*中序遍历代码位置*/
traverse(root.right);
/*后序遍历代码位置*/
}

迭代框架也应该有前中后序代码的位置:

voidtraverse(TreeNoderoot){
while(...){
if(...){
/*前序遍历代码位置*/
}
if(...){
/*中序遍历代码位置*/
}
if(...){
/*后序遍历代码位置*/
}
}
}

我如果想把任何一道二叉树递归解法改成迭代,直接把递归解法中前中后序对应位置的代码复制粘贴到迭代框架里,就可以直接运行,得到正确的结果。

理论上,所有递归算法都可以利用栈改成迭代的形式,因为计算机本质上就是借助栈来迭代地执行递归函数的。

所以本文就来利用「栈」interwetten与威廉的赔率体系 函数递归的过程,总结一套二叉树通用迭代遍历框架

递归框架改为迭代

参加过我的二叉树专项训练的读者应该知道,二叉树的递归框架中,前中后序遍历位置就是几个特殊的时间点:

前序遍历位置的代码,会在刚遍历到当前节点root,遍历root的左右子树之前执行;

中序遍历位置的代码,会在在遍历完当前节点root的左子树,即将开始遍历root的右子树的时候执行;

后序遍历位置的代码,会在遍历完以当前节点root为根的整棵子树之后执行。

0320d1fc-93aa-11ec-952b-dac502259ad0.jpg

如果从递归代码上来看,上述结论是很容易理解的:

voidtraverse(TreeNoderoot){
if(root==null)return;
/*前序遍历代码位置*/
traverse(root.left);
/*中序遍历代码位置*/
traverse(root.right);
/*后序遍历代码位置*/
}

不过,如果我们想将递归算法改为迭代算法,就不能从框架上理解算法的逻辑,而要深入细节,思考计算机是如何进行递归的

假设计算机运行函数A,就会把A放到调用栈里面,如果A又调用了函数B,则把B压在A上面,如果B又调用了C,那就再把C压到B上面……

C执行结束后,C出栈,返回值传给BB执行完后出栈,返回值传给A,最后等A执行完,返回结果并出栈,此时调用栈为空,整个函数调用链结束。

我们递归遍历二叉树的函数也是一样的,当函数被调用时,被压入调用栈,当函数结束时,从调用栈中弹出。

那么我们可以写出下面这段代码模拟递归调用的过程:

//模拟系统的函数调用栈
Stackstk=newStack<>();

voidtraverse(TreeNoderoot){
if(root==null)return;
//函数开始时压入调用栈
stk.push(root);
traverse(root.left);
traverse(root.right);
//函数结束时离开调用栈
stk.pop();
}

如果在前序遍历的位置入栈,后序遍历的位置出栈,stk中的节点变化情况就反映了traverse函数的递归过程(绿色节点就是被压入栈中的节点,灰色节点就是弹出栈的节点):

03342018-93aa-11ec-952b-dac502259ad0.gif

简单说就是这样一个流程:

1、拿到一个节点,就一路向左遍历(因为traverse(root.left)排在前面),把路上的节点都压到栈里

2、往左走到头之后就开始退栈,看看栈顶节点的右指针,非空的话就重复第 1 步

写成迭代代码就是这样:

privateStackstk=newStack<>();

publicListtraverse(TreeNoderoot){
pushLeftBranch(root);

while(!stk.isEmpty()){
TreeNodep=stk.pop();
pushLeftBranch(p.right);
}
}

//左侧树枝一撸到底,都放入栈中
privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
stk.push(p);
p=p.left;
}
}

上述代码虽然已经可以模拟出递归函数的运行过程,不过还没有找到递归代码中的前中后序代码位置,所以需要进一步修改。

迭代代码框架

想在迭代代码中体现前中后序遍历,关键点在哪里?

当我从栈中拿出一个节点p,我应该想办法搞清楚这个节点p左右子树的遍历情况

如果p的左右子树都没有被遍历,那么现在对p进行操作就属于前序遍历代码。

如果p的左子树被遍历过了,而右子树没有被遍历过,那么现在对p进行操作就属于中序遍历代码。

如果p的左右子树都被遍历过了,那么现在对p进行操作就属于后序遍历代码。

上述逻辑写成伪码如下:

privateStackstk=newStack<>();

publicListtraverse(TreeNoderoot){
pushLeftBranch(root);

while(!stk.isEmpty()){
TreeNodep=stk.peek();

if(p的左子树被遍历完了){
/*******************/
/**中序遍历代码位置**/
/*******************/
//去遍历p的右子树
pushLeftBranch(p.right);
}

if(p的右子树被遍历完了){
/*******************/
/**后序遍历代码位置**/
/*******************/
//以p为根的树遍历完了,出栈
stk.pop();
}
}
}

privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
/*******************/
/**前序遍历代码位置**/
/*******************/
stk.push(p);
p=p.left;
}
}

有刚才的铺垫,这段代码应该是不难理解的,关键是如何判断p的左右子树到底被遍历过没有呢?

其实很简单,我们只需要维护一个visited指针,指向「上一次遍历完成的根节点」,就可以判断p的左右子树遍历情况了

下面是迭代遍历二叉树的完整代码框架

//模拟函数调用栈
privateStackstk=newStack<>();

//左侧树枝一撸到底
privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
/*******************/
/**前序遍历代码位置**/
/*******************/
stk.push(p);
p=p.left;
}
}

publicListtraverse(TreeNoderoot){
//指向上一次遍历完的子树根节点
TreeNodevisited=newTreeNode(-1);
//开始遍历整棵树
pushLeftBranch(root);

while(!stk.isEmpty()){
TreeNodep=stk.peek();

//p的左子树被遍历完了,且右子树没有被遍历过
if((p.left==null||p.left==visited)
&&p.right!=visited){
/*******************/
/**中序遍历代码位置**/
/*******************/
//去遍历p的右子树
pushLeftBranch(p.right);
}
//p的右子树被遍历完了
if(p.right==null||p.right==visited){
/*******************/
/**后序遍历代码位置**/
/*******************/
//以p为根的子树被遍历完了,出栈
//visited指针指向p
visited=stk.pop();
}
}
}

代码中最有技巧性的是这个visited指针,它记录最近一次遍历完的子树根节点(最近一次pop出栈的节点),我们可以根据对比p的左右指针和visited是否相同来判断节点p的左右子树是否被遍历过,进而分离出前中后序的代码位置。

PS:visited指针初始化指向一个新 new 出来的二叉树节点,相当于一个特殊值,目的是避免和输入二叉树中的节点重复。

只需把递归算法中的前中后序位置的代码复制粘贴到上述框架的对应位置,就可以把任意递归的二叉树算法改写成迭代形式了

比如,让你返回二叉树后序遍历的结果,你就可以这样写:

privateStackstk=newStack<>();

publicListpostorderTraversal(TreeNoderoot){
//记录后序遍历的结果
Listpostorder=newArrayList<>();
TreeNodevisited=newTreeNode(-1);

pushLeftBranch(root);
while(!stk.isEmpty()){
TreeNodep=stk.peek();

if((p.left==null||p.left==visited)
&&p.right!=visited){
pushLeftBranch(p.right);
}

if(p.right==null||p.right==visited){
//后序遍历代码位置
postorder.add(p.val);
visited=stk.pop();
}
}

returnpostorder;
}

privatevoidpushLeftBranch(TreeNodep){
while(p!=null){
stk.push(p);
p=p.left;
}
}

当然,任何一个二叉树的算法,如果你想把递归改成迭代,都可以套用这个框架,只要把递归的前中后序位置的代码对应过来就行了。

迭代解法到这里就搞定了,不过我还是想强调,除了 BFS 层级遍历之外,二叉树的题目还是用递归的方式来做,因为递归是最符合二叉树结构特点的

说到底,这个迭代解法就是在用栈模拟递归调用,所以对照着递归解法,应该不难理解和记忆。

原文标题:二叉树八股文:递归改迭代通用模板

文章出处:【微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

审核编辑:汤梓红
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4608

    浏览量

    92844
  • 模板
    +关注

    关注

    0

    文章

    108

    浏览量

    20561
  • 函数
    +关注

    关注

    3

    文章

    4329

    浏览量

    62576

原文标题:二叉树八股文:递归改迭代通用模板

文章出处:【微信号:TheAlgorithm,微信公众号:算法与数据结构】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    labview递归使用你尝试过吗?

    递归VI factorial.vi 例子通过当前数与当前数-1的阶乘相乘而得,也就是调用了自己。 数学公式如下,3!=3*(2!)。在这个递归factorial VI,1!和0!
    发表于 01-05 15:07

    用Kei写程序的时候,怎么头文件为AT89X51.H的程序改写成...

    用Kei写程序的时候,怎么头文件为AT89X51.H的程序改写成头文件为REG51.H的。这两种头文件写程序有什么区别?l
    发表于 11-15 21:10

    《C Primer Plus》读书笔记——递归

    ("LEVEL %d: n location %p\n" , n, &n);}输出如下:递归的基本原理每级递归都使用其私有变量(如例子的n)每次函数调用都返回一级(调用他那级
    发表于 02-05 20:06

    快速掌握Python的递归函数与匿名函数调用

    factorial函数调用factorial函数的情况。出现了函数的递归。为了完善上述代码,可以代码的第二部也翻译成代码:  def factorial(n):  1. int
    发表于 07-19 16:22

    LabVIEW递归调用

    一.NI提供的递归调用使用的步骤如下1.VI设置成重载模式2.使用静态调用调用调用VI,实现自身调用看见下图NI自带递归方法二、如果静态调用改成直接调用自身也可得到相同的结果,而且
    发表于 05-18 10:36

    递归最小二乘法

    一、递归最小二乘法递推最小二乘法:当矩阵维数增加时,矩阵求逆运算计算量过大,而且不适合在线辨识。为了减少计算量,并且可以实时地辨识出动态系统的特性,可以最小二乘法转换成参数递推的估计。取N组数据
    发表于 08-27 07:03

    LabVIEW中使用递归算法

    »Open VI Reference。递归VI路径连上,并将options的输入设置为8,这样可以使通过引用调用可重入VI有效。在Open VI Reference图标的type specifier VI
    发表于 04-17 20:11

    C++教程之函数的递归调用

    C++教程之函数的递归调用 在执行函数 f 的过程,又要调用 f 函数本身,称为函数的递归调用;形式上:一个正在执行的函数调用了自身;这种递归
    发表于 05-15 18:00 35次下载

    如何将IP模块整合到System Generator for DSP

    了解如何将Vivado HLS设计作为IP模块整合到System Generator for DSP。 了解如何将Vivado HLS设计保存为IP模块,并了解如何将此IP轻松整合
    的头像 发表于 11-20 05:55 3238次阅读

    如何把C++的源程序改写成C语言

    第一种是C++的面向对象特征去掉,先全部理解源代码的逻辑,然后改写;第二种是在C中保留面向对象的部分特征,用结构体实现类的功能。
    的头像 发表于 05-14 10:08 2918次阅读
    如何把C++的源程序<b class='flag-5'>改写成</b>C语言

    C语言编程如何求出二叉树后序遍历

    题目 已知二叉树前序为 ABDFGCEH 后序序列为 BFDGACEH ,要求输出后序遍历为 FGDBHECA 大体思路 又先序得出根,先序的根后为左树一部分,我们再在序序列里找到先序的根,此处
    的头像 发表于 08-23 11:04 3917次阅读

    如何求递归算法的时间复杂度

    那么我通过一道简单的面试题,模拟面试的场景,来带大家逐步分析递归算法的时间复杂度,最后找出最优解,来看看同样是递归,怎么就写成了O(n)的代码。
    的头像 发表于 07-13 11:30 2260次阅读

    Python支持递归函数

    Python支持递归函数——即直接或间接地调用自身以进行循环的函数。递归是颇为高级的话题,并且它在Python相对少见。然而,它是一项应该了解的有用的威廉希尔官方网站 ,因为它允许程序遍历拥有任意的、不可预知的形状的结构。
    的头像 发表于 02-21 14:28 644次阅读

    如何将Pytorch自训练模型变成OpenVINO IR模型形式

    本文章依次介绍如何将Pytorch自训练模型经过一系列变换变成OpenVINO IR模型形式,而后使用OpenVINO Python API 对IR模型进行推理,并将推理结果通过OpenCV API显示在实时画面上。
    的头像 发表于 06-07 09:31 1985次阅读
    <b class='flag-5'>如何将</b>Pytorch自训练模型变成OpenVINO IR模型<b class='flag-5'>形式</b>

    递归神经网络结构形式主要分为

    结构形式。 Elman网络 Elman网络是一种基本的递归神经网络结构,由Elman于1990年提出。其结构主要包括输入层、隐藏层和输出层,其中隐藏层具有时间延迟单元,可以存储一时刻的隐藏状态。Elman网络的基本原理是
    的头像 发表于 07-05 09:32 519次阅读