//题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和 中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 //思路：分别找到左右子树的前序遍历序列和中序遍历序列，可以用同样的方法分别构建左右子树。可以用递归来完成。 //如何确定前序遍历和中序遍历的左、右子树的子序列

1 struct TreeNode 2 { 3     int val; 4     TreeNode* left; 5     TreeNode* right; 6     TreeNode(int x) :val(x), left(NULL), right(NULL) 7     { 8  9     }10 };11 //关于递归问题，先解决n=1的问题。然后再进行递归。12 class Solution13 {14 public:15     TreeNode* reConstructBinaryTree(vector
     
       pre, vector
      
        in)16     {17         int inlen = in.size();18         if (inlen == 0)19         {20             return NULL;21         }22         vector
       
         left_pre, right_pre, left_in, right_in;23         //创建根节点， 根节点肯定是前序遍历的第一个数24         TreeNode* head = new TreeNode(pre[0]);25         //找到中序遍历根节点所在的位置，存放到gen中26         int gen = 0;27         for (int i = 0; i < inlen; ++i)28         {29             if (in[i] == pre[0])30             {31                 gen = i;32                 break;33             }34         }35         //对于中序遍历，根节点左边的结点位于二叉树左边，根节点右边的结点位于二叉数的右边36         //对二叉树进行归并37         for (int i = 0; i < gen; ++i)38         {39             left_in.push_back(in[i]);40             left_pre.push_back(pre[i + 1]);41         }42         for (int i = gen + 1; i
        
         left = reConstructBinaryTree(left_pre, left_in);49         head->right = reConstructBinaryTree(right_pre, right_in);50         return head;51     }52 };