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

威海网站制作怎么样什么是软文

威海网站制作怎么样,什么是软文,aspsqlserver做网站,江苏网站建设效果好105:从前序与中序遍历序列构造二叉树 啊,好久都没有更新算法题目了。曾今是C,如今是Java,感慨啊。 像树这样的算法题,基本都逃不开递归。递归的思想是:将大任务拆分为小任务。我们不妨构建一个函数&#…

105:从前序与中序遍历序列构造二叉树

啊,好久都没有更新算法题目了。曾今是C++,如今是Java,感慨啊。

像树这样的算法题,基本都逃不开递归。递归的思想是:将大任务拆分为小任务。我们不妨构建一个函数,取名func1(),它实现的功能是:在指定区间内, 找到并构建root节点并返回

如果我们想要构建一棵树,只需要调用func1(),就能够得到树的根节点,那么树的构建过程就可以简化为如下形式:

TreeNode root = new TreeNode();
root.value = value;
root.left = func1(...);
root.right = func1(...)'

通过func1,我们即可计算得到左右节点,具体的逻辑都一样

现在,让我们将视角聚焦于如何构建func1()。函数内容的核心是:构建root节点。构建分为三步: 1.得到root.val,构建root.left,构建root.right。为了解决这个内容,我们先将 前序遍历中序遍历写为以下形式

前序 : 【root,(左子树),(右子树)】
中序 : 【(左子树),root,(右子树)】

如果我们想要确定root节点,我们只需要在前序数组中,获取第一个元素即可。如果我们想要确定左子树长度,右子树长度,我们只需要知道中序中,root节点的index即可

我们假设前序数组的区间范围是: [ l 1 , r 1 ] [ l1, r1 ] [l1,r1]中序是: [ l 2 , r 2 ] [l2, r2] [l2,r2]。root节点在中序的下标是 r o o t I d x I n rootIdxIn rootIdxIn,那么左子树长度 l e f L e n = r o o t I n d I n − l 2 lefLen = rootIndIn - l2 lefLen=rootIndInl2右子树长度 r i g L e n = r 2 − r o o t I n d I n rigLen = r2 - rootIndIn rigLen=r2rootIndIn

rootValue很好获取,前序[l1]。
root.left的获取,我们可以交给递归函数完成。因为root.left,其本质是左子树的root节点,规定func1的计算范围是root节点的左子树范围即可完成计算;
root.right同理。

tip : 笔者习惯将递归函数命名为dfs,但这不是真正的dfs

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public HashMap<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 通过map映射 值-index的方式, 加速root节点在中序数组下标的定位速度for (int i = 0; i < inorder.length; ++i) {map.put(inorder[i], i);}return dfs(preorder, inorder, 0, n - 1, 0, n - 1);}public TreeNode dfs(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {// 递归终止条件, 如果l1 > r1, 表明当区间不存在, 节点值应该赋为nullif (l1 > r1 || l2 > r2) return null;// debugSystem.out.println("l1 = " + l1 + " r1 = " + r1 + " l2 = " + l2 + " r2 = " + r2);// 确定根节点int rootVal = preorder[l1];// 根节点再inorder中的indexint rootIdxIn = map.get(rootVal);System.out.println("rootIdxIn = " + rootIdxIn);// 左区间长度int lefLen = rootIdxIn - l2;// 右区间长度int rigLen = r2 - rootIdxIn;TreeNode root = new TreeNode();root.val = rootVal;root.left = dfs(preorder, inorder, l1 + 1, l1 + lefLen, l2, rootIdxIn - 1);root.right = dfs(preorder, inorder, l1 + lefLen + 1, r1, rootIdxIn + 1, r2);return root;}
}
http://www.mnyf.cn/news/39916.html

相关文章:

  • 如何给网站做右侧导航栏百度指数在线查询
  • 做网站题材网络推广方法
  • 外贸平台是做什么的河南seo网站多少钱
  • 护肤品网站建设目的广告代运营
  • 如何用域名访问网站销售课程视频免费
  • 用asp做旅游网站零基础能做网络推广吗
  • 怎么制作免费网站教程视频网站建设制作过程
  • 什么网站教你做早点百度号码认证平台官网
  • 做网站的公司是接入商吗成都网站排名 生客seo
  • 学专科电子商务后悔死了给你一个网站seo如何做
  • 商城类网站建设步骤新网站推广方法
  • 做网站公司 陕西渭南网站seo技术能不能赚钱
  • 西安学校网站建设一个万能的营销方案
  • pc网站做app京东重庆网站排名公司
  • 电商网站建设服务平台如何免费注册一个网站
  • 制作网制作网站建设的公司电子商务推广
  • 做网站广告收入怎么在网上销售
  • 做网站 怎么赚钱吗网络推广外包代理
  • 金融网站建设内容有趣的软文
  • 天津住房和城乡建设部网站seo网络优化专员是什么意思
  • 做经营网站怎么赚钱国外域名
  • 创建个人网站英文专业培训机构
  • 吉林做网站多少钱成都关键词优化平台
  • 推广链接打开徐州seo招聘
  • 茂名优化网站建设做网络优化的公司排名
  • 高淳区建设局网站安顺seo
  • 网站建设合同的注意事项企业网站seo方案
  • 泰州网站建设公司免费发布广告信息网
  • joomla 1.5 网站建设基础教程人民日报最新头条10条
  • 有什么网站可以下做闭软件seo入门版