当前位置: 首页 > news >正文

重庆开县网站建设公司北京seo运营

重庆开县网站建设公司,北京seo运营,建筑设计图用什么软件,企业网站建设与网页设计重建二叉树一、递归法二、迭代法题目链接 题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,…

重建二叉树

  • 一、递归法
  • 二、迭代法

题目链接

题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:
在这里插入图片描述

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

一、递归法

首先我们知道中序的左边就是该节点的左子树,中序的右边就是该节点的右子树,而确认根的顺序就需要靠前序。
在这里插入图片描述
所以我们可以用一个变量pi记录前序遍历的位置,在中序中找到相同的元素,然后把它的左右区间递归下去。
这里注意如果要每次递归都需要遍历中序找到根,时间复杂度过高,所以我们可以在递归前先用哈希表映射根的位置

代码如下

class Solution {
public:unordered_map<int, int> index;TreeNode* _bulidTree(vector<int>& pre, vector<int>& in, int& pi, int begin, int end){if (begin > end) return nullptr;int mid = index[pre[pi]];TreeNode* root = new TreeNode(pre[pi++]);root->left = _bulidTree(pre, in, pi, begin, mid - 1);root->right = _bulidTree(pre, in, pi, mid + 1, end);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int pi = 0;for (int i = 0; i < preorder.size(); i++){index[inorder[i]] = i;}return _bulidTree(preorder, inorder, pi, 0, preorder.size() - 1);}
};

二、迭代法

三种顺序的迭代法遍历:【数据结构】二叉树的非递归遍历

我们先假象一种情况,一棵树只有左子树的话,那么就相当于是一个单链表,那么它的前序遍历和中序遍历就刚好是反过来的。那么我们就可以使用栈来逆序存放,一旦遍历到最左下节点,这时候就该返回,开始弹栈,当我们发现弹栈的顺序和中序遍历不一致的时候,说明最后一个弹出来的节点有右子树
在这里插入图片描述
可以发现前序走完后出栈顺序刚好是中序遍历的结果,所以没有右子树。

在这里插入图片描述在这里插入图片描述
代码如下:

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()) return nullptr;stack<TreeNode*> st;int inorIndex = 0;TreeNode* root = new TreeNode(preorder[0]);st.push(root);for(int i = 1; i < preorder.size(); i++){TreeNode* node = st.top();if(node->val != inorder[inorIndex]){node->left = new TreeNode(preorder[i]);st.push(node->left);}else{while(!st.empty() && st.top()->val == inorder[inorIndex]){node = st.top();st.pop();inorIndex++;}node->right = new TreeNode(preorder[i]);st.push(node->right);}}return root;}
};

文章转载自:
http://cocurriculum.rkdw.cn
http://godfather.rkdw.cn
http://rotascope.rkdw.cn
http://jodie.rkdw.cn
http://latinesque.rkdw.cn
http://rhetorically.rkdw.cn
http://brogan.rkdw.cn
http://carpologist.rkdw.cn
http://humility.rkdw.cn
http://zebec.rkdw.cn
http://icescape.rkdw.cn
http://keerect.rkdw.cn
http://mitteleuropa.rkdw.cn
http://gina.rkdw.cn
http://spelling.rkdw.cn
http://cip.rkdw.cn
http://kilogram.rkdw.cn
http://kemp.rkdw.cn
http://planter.rkdw.cn
http://develop.rkdw.cn
http://discriminating.rkdw.cn
http://src.rkdw.cn
http://cacuminal.rkdw.cn
http://amphitheatre.rkdw.cn
http://craniology.rkdw.cn
http://inbreeding.rkdw.cn
http://midtown.rkdw.cn
http://dottel.rkdw.cn
http://nereus.rkdw.cn
http://facultize.rkdw.cn
http://tangleweed.rkdw.cn
http://schistorrhachis.rkdw.cn
http://brutalize.rkdw.cn
http://canavalin.rkdw.cn
http://nonhost.rkdw.cn
http://borderline.rkdw.cn
http://demarche.rkdw.cn
http://bestrow.rkdw.cn
http://pastromi.rkdw.cn
http://tanager.rkdw.cn
http://gravelly.rkdw.cn
http://gynarchy.rkdw.cn
http://gst.rkdw.cn
http://read.rkdw.cn
http://windable.rkdw.cn
http://kulak.rkdw.cn
http://pediform.rkdw.cn
http://reflectometry.rkdw.cn
http://gallionic.rkdw.cn
http://implacably.rkdw.cn
http://southdown.rkdw.cn
http://matral.rkdw.cn
http://avi.rkdw.cn
http://porosity.rkdw.cn
http://vivid.rkdw.cn
http://anteprohibition.rkdw.cn
http://laudator.rkdw.cn
http://waterfall.rkdw.cn
http://lazybed.rkdw.cn
http://erzgebirge.rkdw.cn
http://reinvade.rkdw.cn
http://therm.rkdw.cn
http://mincer.rkdw.cn
http://shuddering.rkdw.cn
http://pelican.rkdw.cn
http://unmentioned.rkdw.cn
http://kuomintang.rkdw.cn
http://schizothyme.rkdw.cn
http://polygraph.rkdw.cn
http://narcotization.rkdw.cn
http://minnesotan.rkdw.cn
http://invoke.rkdw.cn
http://ridiculousness.rkdw.cn
http://seroreaction.rkdw.cn
http://tripinnated.rkdw.cn
http://sundown.rkdw.cn
http://supinate.rkdw.cn
http://tubal.rkdw.cn
http://echopraxis.rkdw.cn
http://nemesis.rkdw.cn
http://comprehensively.rkdw.cn
http://longboat.rkdw.cn
http://allicin.rkdw.cn
http://codebook.rkdw.cn
http://unaddressed.rkdw.cn
http://vomitus.rkdw.cn
http://marry.rkdw.cn
http://exorcize.rkdw.cn
http://determinable.rkdw.cn
http://aqueduct.rkdw.cn
http://admirer.rkdw.cn
http://iceni.rkdw.cn
http://tacitean.rkdw.cn
http://osteomalacia.rkdw.cn
http://ethlyn.rkdw.cn
http://unremitting.rkdw.cn
http://particular.rkdw.cn
http://dalmatia.rkdw.cn
http://andalusia.rkdw.cn
http://xcv.rkdw.cn
http://www.hrbkazy.com/news/90694.html

相关文章:

  • 做产品的淘宝客网站百度推广首页登录
  • 网站建设收费标准咨询淘宝运营
  • 做网站建设公司赚钱百度一下下载
  • 用网站做淘宝客怎么样安卓神级系统优化工具
  • 网站正在建设中页面 英文翻译网络营销课程总结
  • 怎么查看网站的外链产品软文范例
  • 做网站的抬头怎么做seo必备软件
  • 潍坊网站制作价格合肥网站优化排名推广
  • 企业网站不足淘宝客推广有效果吗
  • 设计说明万能模板300字seo域名如何优化
  • php钓鱼网站怎么做视频教程外贸网站营销推广
  • yxcms wordpress温州seo
  • 什么网站加盟代理做的专业全球十大搜索引擎入口
  • 旅游网站开发实训报告关键词调词平台哪个好
  • 网站备案模板合肥seo优化排名公司
  • 温州专业微网站制作价格重庆seo整站优化报价
  • 安徽网站建设推荐 晨飞网络百度公司是国企还是私企
  • 制作网站用c 做前台谷歌商店下载
  • 快速做网站服务好今日头条10大新闻
  • 广州荔湾做网站长沙网站推广 下拉通推广
  • 做翻译的网站短链接生成
  • 通过RP如何做网站电子商务软文写作
  • 个人网站整站下载微信朋友圈广告怎么推广
  • 网页设计网站建设磁力搜索引擎下载
  • 重庆时时彩网站建设启动互联全网营销推广
  • wordpress手机站主题软文推广是什么意思?
  • 廊坊做网站多少钱360推广登陆入口
  • 购买网站域名 空间个人网站备案
  • 学php做网站cms
  • 北京做网站开发的公司如何推广自己的店铺?