这是一个创建于 3537 天前的主题，其中的信息可能已经有所发展或是发生改变。
//面试题。
先：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 之前遍历……这叫我放哪里……
当然我肯定是什么地方错了……求大牛指教一二。
先：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 之前遍历……这叫我放哪里……
当然我肯定是什么地方错了……求大牛指教一二。
 |
1
iptux 2014-09-15 22:35:17 +08:00
确定题目没错？
|
 |
2
xjx0524 2014-09-15 22:44:57 +08:00
5不是1的右儿子，3才是，因为前序遍历中3在5前面
|
 |
3
rock_cloud 2014-09-15 22:46:03 +08:00
同楼上，试了半天感觉题目有问题啊。。。
|
|
4
xjx0524 2014-09-15 22:53:15 +08:00
http://localhost-8080.info:8080/1.png
没错啊 这是结果 不会回复图片。。。 |
 |
5
Mutoo 2014-09-15 23:00:33 +08:00
5显然不是1的右儿子，只能说5在1的右子树上。而先序中，最先出现的右子树的元素是3。所以3才是1的右儿子。答案见楼上截图。
|
 |
6
cassyfar 2014-09-16 00:59:07 +08:00
LZ能耐心看懂树的三种遍历再来发问吗
明显3是1的右儿子 |
Select Language