已知前序中序求后序

​

网上看到的一篇关于前序中序求后续的文章，利用递归的方法，内容很不错，值得收藏。

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，

请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。

思路

根据前序遍历的数组，arr[0]为根节点，在中序遍历中找到值等于arr[0]的位置index，则index的左边为此节点的左子树，右边为此节点的右子树。于是递归构建该节点的左右子树。

测试用例：

8

1, 2, 4, 7, 3, 5, 6, 8

4, 7, 2, 1, 5, 3, 8, 6

----------------------------------------

5

1, 2, 3, 4, 5

5, 4, 3, 2, 1

----------------------------------------

5

1, 2, 3, 4, 5

1, 2, 3, 4, 5

----------------------------------------

1

1

1

----------------------------------------

7

1, 2, 4, 5, 3, 6, 7

4, 2, 5, 1, 6, 3, 7

----------------------------------------

7

1, 2, 4, 5, 3, 6, 7

4, 2, 8, 1, 6, 3, 7

//问题描述：已知一个二叉树的前序遍历和中序遍历，求改二叉树的后序遍历，

//二叉树中没有相同的元素，数据为整型。

//例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，

//则重建二叉树并输出它的后序遍历序列。

//思路

//根据前序遍历的数组，arr[0]为根节点，在中序遍历中找到值等于arr[0]的位置index，

//则index的左边为此节点的左子树，右边为此节点的右子树。于是递归构建该节点的左右子树。

/*

输入：

输入可能包含多个测试样例，对于每个测试案例，

输入的第一行为一个整数n(1<=n<=1000)：代表二叉树的节点个数。

输入的第二行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的前序遍历序列。

输入的第三行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的中序遍历序列。

输出：

对应每个测试案例，输出一行：

如果题目中所给的前序和中序遍历序列能构成一棵二叉树，则输出n个整数，代表二叉树的后序遍历序列，每个元素后面都有空格。

如果题目中所给的前序和中序遍历序列不能构成一棵二叉树，则输出”No”。

样例输入输出：

8

1 2 4 7 3 5 6 8

4 7 2 1 5 3 8 6

7 4 2 5 8 6 3 1

8

1 2 4 7 3 5 6 8

4 1 2 7 5 3 8 6

No

*/

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define true 1
 4 #define false 0
 5 typedef int bool1;
 6 
 7 typedef struct BiTreeNode
 8 {
 9 int data;
10 struct BiTreeNode *lchild;
11 struct BiTreeNode *rchild;
12 }BiTreeNode,*BiTree;
13 
14 bool1 CanConstruct;
15 
16 void RebuildTree(BiTree *root,int len,int *PreTraverse,int *InTraverse)
17 {
18 if (PreTraverse == NULL || InTraverse == NULL)
19 {
20 CanConstruct = false;
21 return;
22 }
23 if (len < 1)
24 return;
25 //在中序遍历中找到前序遍历的头结点的左右子结点
26 int index = -1;
27 for (int i = 0; i < len; i++)
28 {
29 if (PreTraverse[0] == InTraverse[i])
30 {
31 index = i;
32 break;
33 }
34 }
35 if(index==-1)//这种情况就是没有找到当前根结点在中序遍历的位置。因此不能重构
36 {
37 CanConstruct = false;
38 return;
39 }
40 //找到了之后就开始构建此结点
41 //为当前结点分配空间
42 *root = (BiTree)malloc(sizeof(BiTreeNode));
43 (*root)->data = PreTraverse[0];
44 (*root)->lchild = NULL;
45 (*root)->rchild = NULL;
46 //接下来开始构建该结点的左右子树。
47 RebuildTree(&(*root)->lchild, index, PreTraverse + 1, InTraverse);
48 RebuildTree(&(*root)->rchild, len - index - 1, PreTraverse + index + 1, InTraverse + index + 1);
49 }
50 
51 
52 void PostOrderTree(BiTree root)
53 {
54 if (!root)
55 return;
56 PostOrderTree(root->lchild);
57 PostOrderTree(root->rchild);
58 printf("%d ", root->data);
59 }
60 
61 
62 int main(void)
63 {
64 int n;
65 while (scanf("%d", &n) && n > 0)
66 {
67 int *PreTraverse = (int *)malloc(sizeof(int)*n);
68 if (!PreTraverse)
69 exit(EXIT_FAILURE);
70 int *InTraverse = (int *)malloc(sizeof(int)*n);
71 if (!InTraverse)
72 exit(EXIT_FAILURE);
73 for (int i = 0; i < n; i++)
74 {
75 
76 cin >>PreTraverse[i];
77 }
78 for (int i = 0; i < n; i++)
79 {
80 
81 cin >> InTraverse[i];
82 }
83 BiTree root;
84 CanConstruct = true;
85 RebuildTree(&root, n, PreTraverse, InTraverse);
86 if (CanConstruct)
87 {
88 PostOrderTree(root);
89 printf("\n");
90 }
91 else
92 {
93 printf("No\n");
94 }
95 }
96 return 0;
97 }