还是那个已知一二叉树先序遍历和中序遍历求出后续遍历的题

[spencerqiu]

//面试题。

先：1 2 4 3 5 7 6
中：4 2 1 5 7 3 6

在上个帖子里，经过各位大牛指导，大概理清了一点思路。

先续遍历第一个肯定是根，于是 1 就是根，中续遍历中 1 右边是 5 ，因为是左根右，且先续第二个为 2 ，所以 2 是左儿子， 5 是右儿子。

因为中续遍历左根右，所以 2 下面的子树就是 4 。

因为先续是根左右，如果 2 的右儿子是 3 ，与中续遍历就不符，于是 3 就在右子树？

然后画出来这样子了？

1
2（L） 5（R）
4（LL）

接下来我却发现…… 3 没地方放了。

因为 3 在右子树上，但是又在 5 之前遍历……这叫我放哪里……

当然我肯定是什么地方错了……求大牛指教一二。

[iptux]

确定题目没错？

[xjx0524]

5不是1的右儿子，3才是，因为前序遍历中3在5前面

[rock_cloud]

同楼上，试了半天感觉题目有问题啊。。。

[xjx0524]

http://localhost-8080.info:8080/1.png
没错啊 这是结果 不会回复图片。。。

[Mutoo]

5显然不是1的右儿子，只能说5在1的右子树上。而先序中，最先出现的右子树的元素是3。所以3才是1的右儿子。答案见楼上截图。

[cassyfar]

LZ能耐心看懂树的三种遍历再来发问吗
明显3是1的右儿子