张家港企业网站建设,wordpress 优化版本,大数据精准营销获客,天站网站建设目录
写在前面#xff1a;
题目#xff1a;
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
写在最后#xff1a; 写在前面#xff1a;
今天的每日一题好难#xff0c;我不会dp啊啊啊啊啊啊。
所以
题目
题目的接口
解题思路
代码
过啦
写在最后 写在前面
今天的每日一题好难我不会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(vectorint preorder, vectorint 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(vectorint preorder, vectorint 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;}//找到根节点后访问前序遍历数组preiprei;//接下来就是依次根据当前的根节点分成左右区间进行递归//[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(vectorint preorder, vectorint inorder) {//设置访问前序遍历的下标走完前序就走完整个二叉树了int prei 0;//创建子函数将中序遍历的区间传过去return _buildTree(preorder, inorder, prei, 0, inorder.size()-1);}
};过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
