【LeetCode】剑指 Offer（2）

目录

写在前面：

题目：

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

---

写在前面：

今天的每日一题好难，我不会dp啊啊啊啊啊啊。

所以，我又来刷剑指 Offer 啦。

题目：剑指 Offer 07. 重建二叉树 - 力扣（Leetcode）

题目的接口：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {}
};

解题思路：

这道题不太简单啊，我得想法是：

通过前序遍历的特性找来确定根节点，

然后对应到中序遍历上，再由中序遍历通过递归的方式重建二叉树。

具体如下：

我们建一个字函数来递归，

设置下标prei 访问前序遍历数组，

使用inbegin和inend确定中序遍历的区间，

然后开展递归。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public://prei走一步少一个节点，需要传引用修改他的值TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& prei, int inbegin, int inend){//当分出来的中序区间走完（不合法），返回空指针//证明该节点没有左/右孩子了if(inbegin > inend){return nullptr;}//将我们要返回的根节点new出来（毕竟要重建二叉树，当然要根节点）TreeNode*root = new TreeNode(preorder[prei]);//让rooti从中序区间开头开始，找出这个区间对应的根节点int rooti = inbegin;//遍历中序区间while(rooti <= inend){//如果找到根节点就跳出循环if(inorder[rooti] == preorder[prei]){break;}rooti++;}//找到根节点后，访问前序遍历数组prei++prei++;//接下来就是依次根据当前的根节点，分成左右区间进行递归//[inbegin, rooti - 1]  rooti  [rooti + 1, inend]//函数的最后两个参数就是区间的头和尾了root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);//最后返回树的根return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//设置访问前序遍历的下标，走完前序就走完整个二叉树了int prei = 0;//创建子函数，将中序遍历的区间传过去return _buildTree(preorder, inorder, prei, 0, inorder.size()-1);}
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。