0


牛客网剑指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) {}
 * };
 */classSolution{public:
    TreeNode*reConstructBinaryTree(vector<int> pre,vector<int> vin){int n=pre.size();int m=vin.size();if(m==0||n==0)returnNULL;//构建根节点,取先序遍历第一个元素
        TreeNode *root=newTreeNode(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、我的题解

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

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

标签: 重构 面试 算法

本文转载自: https://blog.csdn.net/m0_58618795/article/details/126036521
版权归原作者 微凉秋意 所有, 如有侵权,请联系我们删除。

“牛客网剑指offer刷题练习之重构二叉树”的评论:

还没有评论