[剑指Offer] 4.重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
【思路】递归，先找到根结点，再找到左右子树的前序与中序序列进行递归
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) { 13 14 if(pre.size() == 0) 15 return NULL; 16 TreeNode* Root = new TreeNode(pre[0]); 17 18 vector<int> pre1,pre2; 19 vector<int> in1,in2; 20 int root = pre[0]; 21 int root_id = 0; 22 23 //找到根结点在中序序列中位置root_id 24 for(int i = 0;i < in.size();i ++){ 25 if(root == in[i]){ 26 root_id = i; 27 } 28 } 29 30 for(int i = 0;i < root_id;i ++) 31 in1.push_back(in[i]); 32 for(int i = root_id + 1;i < in.size();i ++) 33 in2.push_back(in[i]); 34 35 for(int i = 1;i < in1.size() + 1;i ++) 36 pre1.push_back(pre[i]); 37 for(int i = in1.size() + 1;i < pre.size();i ++) 38 pre2.push_back(pre[i]); 39 40 Root->left = reConstructBinaryTree(pre1,in1); 41 Root->right = reConstructBinaryTree(pre2,in2); 42 43 return Root; 44 45 } 46 };