程序員經典面試題：二叉樹遍歷

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列 {1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并輸出它的后序遍歷序列。 （本題可以直接輸出來，不用先還原出二叉樹）

答案： 遞歸的簡單應用，前序遍歷的根在最前面，在中序遍歷里找到那個數，然后前序序列和中序序列的分解成為兩部分，對這兩部分在遞歸即可。可以直接生成后續遍歷的序列，而不用重構出這棵樹。

#include <iostream>

using namespace std;
int pre[1024],post[1024],in[1024];
bool can(int pre,int in,int *post,int fpre,int fin,int fpost,int len) {
int i;
        if (len <= 0) {
                return true;
        }
        for (i = 0; i < len; ++i) {
                if (pre[fpre] == in[fin + i]) {
                        break;
                }
        }
        if (i >= len) {
                return false;
        }
        if (!can(pre,in,post,fpre + 1,fin,fpost,i)) {
                return false;
        }
        if (!can(pre,in,post,fpre + i + 1,fin + i + 1, fpost + i,len - i - 1)) {
                return false;
        }
        post[fpost + len - 1] = pre[fpre];
        return true;
}
int main() {
int i,n;
        while (scanf("%d",&n) != EOF) {
                for (i = 0; i < n; ++i) {
                        scanf("%d",pre + i);
                }
                for (i = 0; i < n; ++i) {
                        scanf("%d", in + i);
                }
                if (can(pre,in,post,0,0,0,n)) {
                        for (i = 0; i < n; ++i) {
                                printf("%d ",post[i]);
                        }
                        puts("");
                }
                else {
                        puts("No");
                }
        }
        return 0;
}</pre>