• 修复在线人数的显示

  • 修复了Baidu与Github登陆的小Bug

  • 优化网站整体代码布局,提高速度

[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序

猿之力 祭夜ゐ 1个月前 (08-13) 57次浏览 未收录 1个评论 扫描二维码
文章目录[隐藏]

类型

  1. 已知先序与中序遍历,求后序遍历
  2. 已知中序与后序遍历,求先序遍历
  3. 但是已知先序与后序遍历,不可求得中序
  4. 也就是必须知道中序
思路类似,都是先求原始二叉树,再求第三者

1.已知先中,求后序

栗子1:

先序:ABCDEFGH

中序:BDCEAFHG

解题

1.因为先序是先访问根节点,所以A为根节点;

2.因为中序是在树的两边中间访问根节点,并且按大致从左往右的顺序,

所以,BDCE分布在根节点A的左子树,FHG分布在根节点A的右子树;

3.BDCE在先序中是先访问B的,所以B是A的左子树部分的根节点;

因为中序访问时根节点B大致在中间,所以DCE就属于B的右子树部分;

4.同理,C是DCE部分的根节点;D是C的左子树部分,E是C的右子树部分;

5.同样的,也可以判断出A的右子树部分FHG的情况。

答案


栗子2:

先序:ABDGHCEFI

中序:GDHBAECIF

答案


2.已知中后,求先序

提示:
后序遍历是最后访问根节点的

栗子

中序:BDCEAFHG

后序:DECBHGFA

答案


 

 


祭夜blog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序
喜欢 (0)
[1690127128@qq.com]
分享 (0)
发表我的评论
取消评论
OwO表情
贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您也可以使用第三方账号登录


(1)个小伙伴在吐槽
  1. 最讨厌做这种题目了呀
    超人下拉系统2019-08-30 13:58 回复 Windows 7 | Chrome 55.0.2883.87