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

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {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;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。