剑指offer J27 重建二叉树

给定节点数为 n 请重建二叉树并返回其头结点。 如输入前序遍历序列{1、2、4、7、3、5、6、8}和中序遍历序列{4、7、2、1、5、3、8、6}，则重建如下图所示。 提示: 1.vin.length == pre.length 2.pre 和 vin 没有重复元素 3.vin所有出现的元素都出现在这里 pre里 4.只需返回根结点，系统将自动输出整棵树进行答案比较 数据范围：n≤2000，节点的值 -10000<val<10000 要求：空间复杂性 O(n)，时间复杂度 O(n) 输出示例1:

输入:[1、2、4、7、3、5、6、8] 返回值：{1，2，3，4，#，5，6，7，#，#，8} 说明:返回根节点后，系统将输出整个二叉树的对比结果，重建结果如题面图所示

示例2:

输入：[1]，[1] 返回值：{1}

示例3:

输入： [1、2、3、4、5、6、7] 返回值： {1，2，5，3，4，6

在这里，我们先解释一下树木的三种遍历方法。前序遍历从根节点开始，按根-左-右顺序递归遍历树。中序遍历的顺序是左-根-右，后序遍历的顺序是左-右。因此，前序遍历数组的第一项必须是树根pre数组 以[1、2、4、7、3、5、6、8]为例，树根节点的值可确定为1。然后我们在vin[4，7，2，1，5，3，8] 找1，我们按1的位置，很明显，1左边的数组位于左儿子节点(及以下)，1右边的数组位于右儿子节点(及以下)。vin数组分为vin1[4,7,2]和vin2[5，3，8，6]pre可分为数组pre1[2,4,7]和pre如下图所示: 然后只需递归分解数组。

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { 
         public:      ////待建树的头     TreeNode* HEAD;     ///确定根节点，分解pre和vin     void subArry(vector<int> pre,vector<int> vin,TreeNode* treeLocation){ 
                //pre的size为1，不需要直接分解return         if(pre.size()==1){ 
                     return;         }         //子pre数组         vector<int> newPre;         //子vin数组         vector<int> newVin;         //确定树左边的pre和vin         int k1=1,k2=0;         while(vin[k2]!=pre[0]){ 
          newPre.push_back(pre[k1]); newVin.push_back(vin[k2]); k1++;k2++; } if(!newPre.empty()) { 
          //pre第一项为当前根节点值 treeLocation->left=new TreeNode(newPre[0]); //左边继续分解 subArry(newPre, newVin,treeLocation->left); } //确定树右边的pre和vin k2++; newPre.clear(); newVin.clear(); while(k1<pre.size()&&k2<vin.size()){ 
          newPre.push_back(pre[k1]); newVin.push_back(vin[k2]); k1++;k2++; } if(!newPre.empty()) { 
          //pre第一项为当前根节点值 treeLocation->right=new TreeNode(newPre[0]); //右边继续分解 subArry(newPre, newVin,treeLocation->right); } } //方法入口 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { 
          if(!pre.empty()){ 
         //当pre为空直接跳过递归,返回HEAD(HEAD为null) //pre第一项为当前根节点值 HEAD=new TreeNode(pre[0]); subArry(pre,vin,HEAD); } return HEAD; } };