牛客网剑指offer刷题练习之重构二叉树

✅作者简介：C/C++领域新星创作者，为C++和java奋斗中
✨个人社区：微凉秋意社区
🔥系列专栏：牛客刷题专栏
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

今天分享用C++做算法题的经验，题目来自于牛客网《剑指offer》专栏里的一道二叉树中等难度的算法题。牛客网是一个资源丰富且能够免费刷题、面试的网站，强烈推荐小伙伴们使用，链接已经放在文章开头了。

重建二叉树问题

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、我的题解

我们在做二叉树相关题目时，应首先想到递归的方法。本题的递归思路就是已知先序的第一个元素作为树的根结点，再利用中序遍历来分割序列，将分割好的序列放进容器内再次调用重建函数，直到最后一个根结点没有了左右子树，开始回溯，将整个左子树和右子树连接到根节点上，程序结束，这道题也就解决了，建议小伙伴们结合题目解析里的图片思考，攻破难题。

写在最后
二叉树的题目大都是和递归有关，认真的做一道题比盲目刷几十道收获要大得多，勤做笔记，善于用思考才会变强！