返回顶部

收藏

程序员经典面试题:二叉树遍历

更多
#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;
}

标签:二叉树,面试题,C语言

收藏

0人收藏

支持

0

反对

0

发表评论