牛客网剑指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、我的题解

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

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