面试题6：重建二叉树

题目链接：http://ac.jobdu.com/problem.php?pid=1385

思路：前序遍历结果的第一个数字就是根节点，找到根节点在中序遍历中
的位置，则该位置左边的即为左子树的中序遍历的结果。显然我们很容易
就可以得到左右子树的前序和中序遍历结果，我们可以使用递归来构建。

小知识：

preorder 前序序列

inorder 中序序列

postoredr 后序序列

code:

 1 #include <cstdio>
 2 using namespace std;
 3 const int MAXN = 1005;
 4 struct BinaryTreeNode
 5 {
 6     int             nValue;
 7     BinaryTreeNode* nLeft;
 8     BinaryTreeNode* nRight;
 9 };
10  
11 bool flag = true;  // 标志是否构建成功
12  
13 BinaryTreeNode* BuildTree(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
14 {
15     if (flag == false) return NULL;
16     int rootValue = startPreorder[0];
17     BinaryTreeNode* root = new BinaryTreeNode();
18     root->nValue = rootValue;
19     root->nLeft = root->nRight = NULL;
20  
21     // 非法数据预判
22     if (startPreorder == endPreorder)
23     {
24         if (startInorder == endInorder && *startPreorder == *startInorder) return root;
25         else
26         {
27             flag = false;
28             return NULL;
29         }
30     }
31     // 在中序遍历中找到根节点
32     int* rootInder = startInorder;
33     while (rootInder <= endInorder && *rootInder != rootValue) ++rootInder;
34     // 非法数据检查
35     if (rootInder == endInorder && *rootInder != rootValue)
36     {
37         flag = false;
38         return NULL;
39     }
40     int leftLength = rootInder - startInorder;
41     int* leftPreorderEnd = startPreorder + leftLength;
42     if (leftLength > 0)
43     {
44         // 构建左子树
45         root->nLeft = BuildTree(startPreorder + 1, leftPreorderEnd, startInorder, rootInder - 1);
46     }
47     if (leftLength < endPreorder - startPreorder)
48     {
49         // 构建右子树
50         root->nRight = BuildTree(leftPreorderEnd + 1, endPreorder, rootInder + 1, endInorder);
51     }
52     return root;
53 }
54  
55 void postorderTravel(BinaryTreeNode* root)
56 {
57     // 递归遍历
58     if (root != NULL)
59     {
60         postorderTravel(root->nLeft);
61         postorderTravel(root->nRight);
62         printf("%d ", root->nValue);
63     }
64 }
65  
66 int main()
67 {
68     int preOrder[MAXN];
69     int inOrder[MAXN];
70     int n;
71     while (scanf("%d", &n) != EOF)
72     {
73         for (int i = 0; i < n; ++i) scanf("%d", &preOrder[i]);
74         for (int i = 0; i < n; ++i) scanf("%d", &inOrder[i]);
75         flag = true;
76         BinaryTreeNode* root = BuildTree(preOrder, preOrder + n - 1, inOrder, inOrder + n - 1);
77         if (flag == false) printf("No");
78         else postorderTravel(root);
79         printf("
");
80     }
81     return 0;
82 }