重建二叉树问题
1、题目描述
输出示例：
2、题目解析
1、分析：
对于二叉树的前序遍历，我们知道序列的第一个元素必定是根节点的值，因为序列没有重复的元素，因此中序遍历中可以找到相同的这个元素，而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分，如下图所示：
我们可以发现，数字1是根节点，并将二叉树分成了(247)和(3568)两棵子树，而子树的的根也是相应前序序列的首位，比如左子树的根是数字2，右子树的根是数字3，这样我们就可以利用前序遍历序列找子树的根节点，利用中序遍历序列区分每个子树的节点数。
2、具体步骤：
先根据前序遍历第一个点建立根节点。
然后遍历中序遍历找到根节点在数组中的位置。
再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。
直到子树的序列长度为0，结束递归。
3、代码实现
/** * 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* reConstructBinaryTree(vector<int> pre,vector<int> vin) { int n=pre.size(); int m=vin.size(); if(m==0||n==0) return NULL; //构建根节点，取先序遍历第一个元素 TreeNode *root=new TreeNode(pre[0]); for(int i=0;i<m;i++){ //找到中序遍历中的前序第一个元素 if(pre[0]==vin[i]){ //左子树前序遍历 vector<int> leftpre(pre.begin()+1,pre.begin()+1+i); //左子树中序遍历 vector<int> leftvin(vin.begin(),vin.begin()+i); //建立左子树 root->left=reConstructBinaryTree(leftpre, leftvin); //右子树前序遍历 vector<int> rightpre(pre.begin()+1+i,pre.end()); //右子树中序遍历 vector<int> rightvin(vin.begin()+i+1,vin.end()); //构建右子树 root->right=reConstructBinaryTree(rightpre, rightvin); } } return root; } };
注释部分是牛客网的为我们提供的已经封装的结构体，里面有整型val存放数据，left和right是左右子树的指针，还有一个Tree(int x)的构造，利用初始化列表来使创建的结点左右子树指针为空。
下面的Solution类是题目的解决方案，初次刷题或者刚刷题不久的朋友要熟悉这个模式，此外函数声明也会为我们准备好：返回值是一个根节点，函数名为reConstructBinaryTree，参数列表的第一个形参是pre可变长数组，存放构建二叉树的前序序列，第二个参数是vin可变长数组，存放构建二叉树的中序序列，下面的具体实现我已经标上了重要注释，请朋友们自行消化吸收。如果对于可变长数组vector容器不了解甚至不会用，可以看我之前的关于解析vector容器的文章，C++算法题对于vector容器非常青睐，一定要有比较熟悉的理解才行。
4、我的题解
我们在做二叉树相关题目时，应首先想到递归的方法。本题的递归思路就是已知先序的第一个元素作为树的根结点，再利用中序遍历来分割序列，将分割好的序列放进容器内再次调用重建函数，直到最后一个根结点没有了左右子树，开始回溯，将整个左子树和右子树连接到根节点上，程序结束，这道题也就解决了，建议小伙伴们结合题目解析里的图片思考，攻破难题。
