当前位置: 首页 > news >正文

从中序与后序遍历序列构建二叉树的迭代解法

如题,在今天刷题时碰到了这样一道二叉树的题目,原题地址在这里:
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal?envType=study-plan-v2&envId=top-interview-150
在官方题解中已经给出了使用递归的解法,讲解还是比较清晰的,但是我在理解迭代做法的时候却觉得很难理解,在这里详细拆解一下步骤并给出C#源代码。

给出本次分析要用的示例二叉树:

        3/ \9  20/ \   \15 10   7/ \5   8\4

保证树的每个节点的值不重复。
它的中序遍历和后序遍历分别为

inorder = [15, 9, 10, 3, 20, 5, 7, 8, 4]
postorder = [15, 10, 9, 5, 4, 8, 7, 20, 3]


先说结论:我们使用一个指针index(初始指向中序的最后一个位置)和一个栈(维护二叉树的层次结构,栈顶为当前正在分析的节点)辅助构建这个二叉树。我们将后序遍历的最后一个节点入栈,然后从倒数第二个开始,往前依次检查每一个节点。


对于栈顶节点:
*如果栈顶节点和index指向的节点不一致,代表正在检查的节点不可能是栈顶节点的左儿子,于是将这个节点作为栈顶节点的右儿子入栈。
*如果栈顶节点和index指向的节点一致,代表正在检查的节点不可能是栈顶节点的右儿子,但不一定是左儿子,而可能是栈顶节点某个祖先节点的左子树中的某个神必节点,所以需要找到是哪个祖先节点的左子树,于是将栈顶节点弹出,并将index左移一位,检查index指向的节点是不是正在检查的那个节点,如果是,那么刚刚弹出的那个节点就是该节点的父节点,所以将该节点作为刚刚弹出的那个节点的左儿子入栈。如果不是则重复刚刚的操作,继续弹出栈顶节点并左移index。如果直到栈空都还没找到对应的index,那就代表这个节点不可能在栈顶节点的右边,而只能是左子树的一点,而且只可能是栈顶节点的左儿子,于是将其作为刚刚弹出的那个栈顶节点的左儿子入栈。
*如果将后序遍历的最后一个节点入栈,算法就结束了,我们已经构建完成。


以上两个原则(除了最后一个结束条件算凑数的)是怎么来的呢?
首先看中序遍历和后序遍历的特点:
中序遍历:按照“左子树->根节点->右子树”的顺序遍历,也就是说对于遍历列表中的某个节点,左边的全是左子树的节点,右边全是右子树的节点。如果我们把这个列表倒过来(至于为什么要倒过来,等会看看后序遍历的特点就知道了),那就是按照“右子树->根节点->左子树”的顺序遍历,已经遍历过的节点一定在现在正在检查的这个节点的右子树中。
后序遍历:按照“左子树->右子树->根节点”的顺序遍历,如果把遍历列表倒过来,第一个就是整棵树的根节点,然后按顺序可以找到根节点的右子树,最后是左子树。


那么我们可以开始工作了,用栈保存节点,是为了从根节点开始向下分析,先找右子树。右子树找完,可能会有几个节点有左子树,那么我们可以将没有左子树的节点弹出,找到有左子树的那个层次去构建左子树,然后继续从这个左子树开始往它的右子树走,重复以上分析,最后完成整棵树的构建。采用这个顺序,是因为后序遍历倒过来就如刚刚所说,是按照根节点-右子树-左子树来走的。
第一个入栈的节点是根节点3,然后我们检查3的下一个节点(也就是20),因为当前index指向的是inorder的最后一个,也就是4,根据原则一,我们认为20是3的右儿子。这是因为根据中序遍历的特点,如果3没有右子树,那么3应该是中序遍历的最后一个节点,那inorder的最后一个节点应该是3才对,所以这不可能,20一定是3的右儿子,入栈吧。
同理20也不会是最右边的节点,不然中序遍历的最后一个应该是20,所以20的右子树肯定还有东西,7作为20的右儿子入栈。
7和8也同理,就不用说了。轮到检查5,此时栈顶节点是4……
这里插个题外话,我写到这里的时候有点懵,因为不知道4这个节点是不是需要特殊情况讨论,后来想半天才反应过来,我们检查的节点是栈顶节点的下一个,我们对比和index指向的节点是不是一样的那个节点,是栈顶节点而不是检查中的节点(所以我这个“检查”的措辞用得是真垃圾,但是这个文章没有方便的F2重命名,就算了8 XD)
回到正题,检查节点5,此时栈顶为4,终于检查到了一个和index指向节点一样的栈顶节点,这意味着什么呢,由于中序遍历按照“左中右”的顺序遍历,最右边的节点不可能还有右子树了,所以4不可能还有右子树,所以我们检查的这个5要么是4的左子树中的某一点,要么是4的某个祖先节点的左子树中的某一点,现在我们可以开始找是哪个祖宗了。
现在栈里面从底部开始按顺序为3-20-7-8-4,只要按顺序弹出,我们就可以从3的右子树的底部往上一层一层找5是谁的左儿子……(顺带一提为什么一定是左儿子呢,有点长加一段吧)
如果这个5在节点3和节点4中间某一层:它一定是栈里面某个节点的左儿子,因为按照后序遍历,5所在层级的遍历顺序是这样的:左子树->右子树->节点5->父节点的右子树->父节点,所以我们刚刚已经找完4后面的节点了,所以一定会先找到5才会找到5的右子树,然后是5的左子树,所以我们才可以断定5一定是某个节点的左儿子。
我们在一层一层弹栈的时候(还记得吗,每次index左移一位并将栈顶节点弹出,意味着我们从树右边底部开始往前面回溯了)就会排除完右子树的节点,在弹出父节点的时候会发现index指向的新节点和栈顶节点不一样诶,这意味着index指针在反向的中序遍历过程中,右边子树都已经逛完了,刚找到了5的父节点(7),现在来到5这个节点了,所以我们可以断定5就是7的左儿子,将其作为7的左儿子入栈。那么5就会作为一个全新的子树根节点,开始重复之前的操作,从右子树开始检查……到这一步是不是有点递归那种思想的感觉了?如果是的话那离算法完成已经不远了。
现在我们讨论最后一种情况(实际上和上一点是同样的情况)也就是栈空,这意味着我们要找的节点一定是刚弹出的那个节点的左儿子,毕竟栈都弹空了,栈顶节点的右子树肯定已经找完了,那只能是刚弹出的那个栈顶节点的左儿子咯。


以下是C#源代码(顺带一提我是从写完写到这里才开始写代码,因为真的太tm难懂了,好不容易整理这一大堆废话才明白自己在说什么各位读者不要介意):

        public TreeNode BuildTree(int[] inorder, int[] postorder){int index = inorder.Length - 1;Stack<TreeNode> stack = [];TreeNode top, current, result = new(postorder[^1]);//先将后序遍历的最后一个元素作为根节点入栈,从倒数第二个元素开始检查stack.Push(result);for (int i = postorder.Length - 2; i >= 0; i--){top = stack.Peek();current = new(postorder[i]);//如果栈顶节点和index指向的节点不一致,//代表正在检查的节点不可能是栈顶节点的左儿子,//将这个节点作为栈顶节点的右儿子入栈if (top.val != inorder[index]){top.right = current;stack.Push(current);}//如果栈顶节点和index指向的节点一致,则开始找祖宗环节else{while (stack.Count > 0 && stack.Peek().val == inorder[index]){top = stack.Pop();index--;}//找到了祖先节点,将这个节点作为栈顶节点的左儿子入栈top.left = current;stack.Push(current);}}return result;}
http://www.hskmm.com/?act=detail&tid=19312

相关文章:

  • 安装 HuggingFace datasets 模块、包、库
  • 使用 SignalR 向前端推送图像
  • 隐私保护与联邦学习文献阅读
  • Java实习模拟面试|离散数学|概率论|金融英语|数据库实战|职业规划|期末冲刺|今日本科计科要闻速递:技术分享与学习指南 - 实践
  • 学术写作
  • 2025.9.27
  • 9.27(课后作业
  • 详细介绍:【序列晋升】45 Spring Data Elasticsearch 实战:3 个核心方案破解索引管理与复杂查询痛点,告别低效开发
  • 详细介绍:python+django/flask+uniapp基于微信小程序的瑜伽体验课预约系统
  • 生成算数问题*30
  • 6379:统计学生信息(使用动态链表完成)
  • 详细介绍:云原生 vs 传统部署
  • 单链表
  • 课后作业1-3
  • GNSS精度判断和协方差矩阵 - MKT
  • Insightly模板页面存储型XSS漏洞分析与复现
  • 记录 | 关于陪伴型交互AI的一些探讨
  • 课后作业
  • luogu P1719 最大加权矩形
  • CF2065D Skibidus and Sigma
  • 微信二次开发个人号api
  • 课后作业2(动手动脑,课后实验性问题)
  • 从零开始构建图注意力网络:GAT算法原理与数值实现详解
  • 关于Leetcode 812题的简单思考
  • Laravel5.8 利用 snappyPDF 生成PDF文件
  • 25秋周总结4
  • Python 潮流周刊#121:工程师如何做出高效决策?
  • 饥荒联机版
  • iSCSI网络存储——基于VM17下麒麟V10SP1与SP2的共享配置
  • 微信二次开发文档