//面试题。
先：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 之前遍历……这叫我放哪里……
当然我肯定是什么地方错了……求大牛指教一二。
Select Language