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\n", pNode->m_nValue); 44  45         if (pNode->m_pLeft != NULL) 46             printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue); 47         else 48             printf("left child is null.\n"); 49         if (pNode->m_pRight != NULL) 50             printf("value of its right childe is : %d.\n", pNode->m_pRight->m_nValue); 51         else 52             printf("right child is null.\n"); 53     } 54     else 55     { 56  57         printf("this node is null.\n"); 58  59     } 60     printf("\n"); 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 = http://www.mamicode.com/startPreorder[0]; 99     BinaryTreeNode *root = new BinaryTreeNode();100     root->m_nValue =http://www.mamicode.com/ 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         else109             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:\n", testName);142     printf("The preorder sequence is: ");143     for (int i = 0; i < length; ++i)144         printf("%d ", preorder[i]);145     printf("\n");146 147     printf("The inorder sequence is:");148     for (int i = 0; i < length; ++i)149         printf("%d ", inorder[i]);150     printf("\n");151 152     try153     {154         BinaryTreeNode *root = Construct(preorder, inorder, length);155         PrintTree(root);156 157     }158     catch (std::exception &expection)159     {160         printf("Invalid Input.\n");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 8193 The inorder sequence is:4 7 2 1 5 3 8 6194 value of this node is : 1195 value of its left child is: 2.196 value of its right childe is : 3.197 198 value of this node is : 2199 value of its left child is: 4.200 right child is null.201 202 value of this node is : 4203 left child is null.204 value of its right childe is : 7.205 206 value of this node is : 7207 left child is null.208 right child is null.209 210 value of this node is : 3211 value of its left child is: 5.212 value of its right childe is : 6.213 214 value of this node is : 5215 left child is null.216 right child is null.217 218 value of this node is : 6219 value of its left child is: 8.220 right child is null.221 222 value of this node is : 8223 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 tree241 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 pre276         //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 };