题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树
问题描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。
如下图所示，前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。
同样，在前序遍历的序列中，根结点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。
既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。
完整的代码示例如下，方式一使用数组存储前序遍历序列和中序遍历序列；方式二使用容器存储。
1 /* 2 题目描述 3 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 4 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 5 */ 6 7 /* 8 思路： 9 先序遍历的第一个元素为根节点，在中序遍历中找到这个根节点，从而可以将中序遍历分为左右两个部分， 10 左边部分为左子树的中序遍历，右边部分为右子树的中序遍历，进而也可以将先序遍历除第一个元素以外的剩余部分分为两个部分， 11 第一个部分为左子树的先序遍历，第二个部分为右子树的先序遍历。 12 由上述分析结果，可以递归调用构建函数，根据左子树、右子树的先序、中序遍历重建左、右子树。 13 */ 14 /* 15 Time:2016年9月9日11:57:07 16 Author:CodingMengmeng 17 */ 18 19 /* 20 方式一： 21 数组+递归 22 */ 23 #include <iostream> 24 using namespace std; 25 26 //树结点结构体 27 struct BinaryTreeNode 28 { 29 30 int m_nValue; 31 BinaryTreeNode* m_pLeft; 32 BinaryTreeNode* m_pRight; 33 34 35 36 }; 37 38 //打印树结点 39 void PrintTreeNode(BinaryTreeNode *pNode) 40 { 41 if (pNode != NULL) 42 { 43 printf("value of this node is : %d ", pNode->m_nValue); 44 45 if (pNode->m_pLeft != NULL) 46 printf("value of its left child is: %d. ", pNode->m_pLeft->m_nValue); 47 else 48 printf("left child is null. "); 49 if (pNode->m_pRight != NULL) 50 printf("value of its right childe is : %d. ", pNode->m_pRight->m_nValue); 51 else 52 printf("right child is null. "); 53 } 54 else 55 { 56 57 printf("this node is null. "); 58 59 } 60 printf(" "); 61 } 62 void PrintTree(BinaryTreeNode *pRoot) 63 { 64 PrintTreeNode(pRoot); 65 // 66 if (pRoot != NULL) 67 { 68 if (pRoot->m_pLeft != NULL) 69 PrintTree(pRoot->m_pLeft); 70 if (pRoot->m_pRight != NULL) 71 PrintTree(pRoot->m_pRight); 72 } 73 } 74 75 /* 76 preorder 前序遍历 77 inorder 中序遍历 78 79 */ 80 81 BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder); 82 BinaryTreeNode *Construct(int *preorder, int *inorder, int length)//输入前序序列，中序序列和序列长度 83 { 84 if (preorder == NULL || inorder == NULL || length <= 0) 85 return NULL; 86 return ConstructCore(preorder, preorder + length - 1, inorder, inorder + length - 1); 87 88 } 89 90 // startPreorder 前序遍历的第一个节点 91 // endPreorder 前序遍历的最后后一个节点 92 // startInorder 中序遍历的第一个节点 93 // startInorder 中序遍历的最后一个节点 94 95 BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder) 96 { 97 // 前序遍历序列的第一个数字是根结点的值 98 int rootValue = startPreorder[0]; 99 BinaryTreeNode *root = new BinaryTreeNode(); 100 root->m_nValue = rootValue; 101 root->m_pLeft = root->m_pRight = NULL; 102 103 // 只有一个结点 104 if (startPreorder == endPreorder) 105 { 106 if (startInorder == endInorder && *startPreorder == *startInorder) 107 return root; 108 else 109 throw std::exception("Invalid input."); 110 } 111 112 //有多个结点 113 // 在中序遍历中找到根结点的值 114 int *rootInorder = startInorder; 115 while (rootInorder <= endInorder && *rootInorder != rootValue) 116 ++rootInorder; 117 if (rootInorder == endInorder && *rootInorder != rootValue) 118 throw std::exception("Invalid input"); 119 // 120 int leftLength = rootInorder - startInorder; //中序序列的左子树序列长度 121 int *leftPreorderEnd = startPreorder + leftLength; //左子树前序序列的最后一个结点 122 if (leftLength > 0) 123 { 124 // 构建左子树 125 root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, startInorder, rootInorder - 1); 126 } 127 if (leftLength < endPreorder - startPreorder) //（中序序列）若还有左子树，则左子树序列长度应等于当前前序序列的长度 128 //若小于，说明已无左子树，此时建立右子树 129 { 130 // 构建右子树 131 root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder, rootInorder + 1, endInorder); 132 } 133 // 134 return root; 135 } 136 137 // 测试代码 138 void Test(char *testName, int *preorder, int *inorder, int length) 139 { 140 if (testName != NULL) 141 printf("%s Begins: ", testName); 142 printf("The preorder sequence is: "); 143 for (int i = 0; i < length; ++i) 144 printf("%d ", preorder[i]); 145 printf(" "); 146 147 printf("The inorder sequence is:"); 148 for (int i = 0; i < length; ++i) 149 printf("%d ", inorder[i]); 150 printf(" "); 151 152 try 153 { 154 BinaryTreeNode *root = Construct(preorder, inorder, length); 155 PrintTree(root); 156 157 } 158 catch (std::exception &expection) 159 { 160 printf("Invalid Input. "); 161 } 162 } 163 164 // 普通二叉树 165 // 1 166 // / 167 // 2 3 168 // / / 169 // 4 5 6 170 // / 171 // 7 8 172 void Test1() 173 { 174 const int length = 8; 175 int preorder[length] = { 1, 2, 4, 7, 3, 5, 6, 8 }; 176 int inorder[length] = { 4, 7, 2, 1, 5, 3, 8, 6 }; 177 178 Test("Test1", preorder, inorder, length); 179 } 180 181 int main() 182 { 183 Test1(); 184 system("pause"); 185 return 0; 186 } 187 188 /* 189 输出结果： 190 ---------------------------------------------------------------- 191 Test1 Begins: 192 The preorder sequence is: 1 2 4 7 3 5 6 8 193 The inorder sequence is:4 7 2 1 5 3 8 6 194 value of this node is : 1 195 value of its left child is: 2. 196 value of its right childe is : 3. 197 198 value of this node is : 2 199 value of its left child is: 4. 200 right child is null. 201 202 value of this node is : 4 203 left child is null. 204 value of its right childe is : 7. 205 206 value of this node is : 7 207 left child is null. 208 right child is null. 209 210 value of this node is : 3 211 value of its left child is: 5. 212 value of its right childe is : 6. 213 214 value of this node is : 5 215 left child is null. 216 right child is null. 217 218 value of this node is : 6 219 value of its left child is: 8. 220 right child is null. 221 222 value of this node is : 8 223 left child is null. 224 right child is null. 225 226 请按任意键继续. . . 227 ---------------------------------------------------------------- 228 229 */ 230 231 /* 232 方式二：容器+递归 233 */ 234 235 #include <iostream> 236 #include <vector> 237 using namespace std; 238 239 240 // Definition for binary tree 241 struct TreeNode { 242 int val; 243 TreeNode *left; 244 TreeNode *right; 245 TreeNode(int x) : val(x), left(NULL), right(NULL) {} 246 }; 247 248 /* 先序遍历第一个位置肯定是根节点node， 249 250 中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组 251 252 另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组 253 254 把四个数组找出来，分左右递归调用即可 255 256 */ 257 258 class Solution { 259 260 public: 261 262 struct TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) { 263 264 int in_size = in.size();//获得序列的长度 265 266 if (in_size == 0) 267 268 return NULL; 269 270 //分别存储先序序列的左子树，先序序列的右子树，中序序列的左子树，中序序列的右子树 271 vector<int> pre_left, pre_right, in_left, in_right; 272 273 int val = pre[0];//先序遍历第一个位置肯定是根节点node,取其值 274 //新建一个树结点，并传入结点值 275 TreeNode* node = new TreeNode(val);//root node is the first element in pre 276 //p用于存储中序序列中根结点的位置 277 int p = 0; 278 279 for (p; p < in_size; ++p){ 280 281 if (in[p] == val) //Find the root position in in 282 283 break; //找到即跳出for循环 284 285 } 286 287 for (int i = 0; i < in_size; ++i){ 288 289 if (i < p){ 290 //建立中序序列的左子树和前序序列的左子树 291 in_left.push_back(in[i]);//Construct the left pre and in 292 293 pre_left.push_back(pre[i + 1]);//前序第一个为根节点,+1从下一个开始记录 294 295 } 296 297 else if (i > p){ 298 //建立中序序列的右子树和前序序列的左子树 299 in_right.push_back(in[i]);//Construct the right pre and in 300 301 pre_right.push_back(pre[i]); 302 303 } 304 305 } 306 //取出前序和中序遍历根节点左边和右边的子树 307 //递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点 308 node->left = reConstructBinaryTree(pre_left, in_left); 309 310 node->right = reConstructBinaryTree(pre_right, in_right); 311 312 return node; 313 314 } 315 316 };