遍历结果逆推二叉树

答案:1 悬赏:10 手机版

解决时间 2021-02-04 00:32

提问者网友：却不属于对方
2021-02-03 00:33

遍历结果逆推二叉树

最佳答案

五星知识达人网友：舍身薄凉客
2021-02-03 02:04

由两种遍历所得的顺序能唯一确定一棵二叉树，比如给定了一颗二叉树的先序序列是:ABDECFG,中序序列是：DBEAFCG，由先序序列可以确定该二叉树根为A,因为先序遍历的顺序是从根到左子树再到右子树，然后从中序序列中，可以得知DBE在A的左子树，而FCG在A的右子树，由于在先序序列中B紧跟在A后，所以B肯定是A左子树的树根，再看中序序列里，A的左子树是DBE，由中序序列遍历的顺序为：左子树，双亲，右子树，可知D为B的左子树，E为B的右子树，同样可以分析树根A的右子树，先序序列中ABDE已经将树根和左子树遍历完成，所以剩下的CFG是右子树的先序遍历序列，可知C为右子树的树根，F为C的左子树，G为C的右子树，所以该二叉树按层序遍历的顺序应该是ABCDEFG。追问。。。。。能不能正儿八经看看问题？

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息