二叉樹算法：中序、后序推導先序（數組遞歸實現 【*模板】）

中根序列和后根序列重建二叉樹

描述

我們知道如何按照三種深度優先次序來周游一棵二叉樹，來得到中根序列、前根序列和后根序列。反過來，如果給定二叉樹的中根序列和后根序 列，或者給定中根序列和前根序列，可以重建一二叉樹。本題輸入一棵二叉樹的中根序列和后根序列，要求在內存中重建二叉樹，最后輸出這棵二叉樹的前根序列。

用不同的整數來唯一標識二叉樹的每一個結點，下面的二叉樹

中根序列是9 5 32 67

后根序列9 32 67 5

前根序列5 9 67 32

先讀入一個數n代表中序和后序均有n個元素。

接著輸入中序序列，在輸入后序序列。

輸出先序序列。

輸入：

4

9 5 32 67

9 32 67 5

輸出：

5 9 67 32

#include <stdio.h>
#include <string.h>void build(int len, int *s1, int *s2, int *s)
{int p;int i;if(len<=0)return;else{for(i=0; i<len; i++){if(s1[i]==s2[len-1]){p = i;}}build(p, s1, s2, s+1);build(len-p-1, s1+p+1, s2+p, s+p+1);s[0] = s2[len-1];}
}int main()
{int i;int s1[1000], s2[1000], s3[1000];int n;while(scanf("%d", &n)!=EOF){for(i=0; i<n; i++){scanf("%d", &s1[i] );}for(i=0; i<n; i++){scanf("%d", &s2[i] );}build(n, s1, s2, s3 );for(i=0; i<n; i++){printf("%d%c", s3[i], i==n-1?'\n':' ' );}}return 0;
}

?