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

手机app开发培训seo排名优化技术

手机app开发培训,seo排名优化技术,深圳网站搭建电话,云主机还需要买电脑吗这道题看完题想了几分钟就想到大概的思路了,但是在写的时候有很多细节没注意出了很多问题,然后写了1个多小时,其实这道题挺简单的。 首先,最基本的知识,先序遍历是根左右,中序遍历是左根右,那么…

 这道题看完题想了几分钟就想到大概的思路了,但是在写的时候有很多细节没注意出了很多问题,然后写了1个多小时,其实这道题挺简单的。

首先,最基本的知识,先序遍历是根左右,中序遍历是左根右,那么我们一眼可以知道:根节点是先序遍历的第一个节点,然后又可以在中序遍历中找到这个根节点(树中每个val都不相等),中序遍历中根节点的左变是左子树,根节点的右遍是右子树。

那么这个题目应该怎么解呢?首先,对于树的题目要么递归要么用队列或栈,我选择用递归。根据上面发现的几个点,我想到了递归函数:

public TreeNode dfs(int[] preorder, int[] inorder)

通过这两个遍历序列我们可以创建出根节点,然后我们在从preorder和inorder中找出来左子树的leftPreorder和leftInorder以及右子树的rightPreorder和rightInorder,然后利用递归

root.left=dfs(leftPreorder, leftInorder);
root.right = dfs(rightPreorder, rightInorder);

大体上的思路就是这样,那么我们如何找出左右子树的前序和中序的遍历序列呢?

首先中序遍历是非常简单的,中序遍历是左根右的顺序,它对于每颗树都是根左右的顺序,所以‘左’就是左子树的中序遍历结果,所以我们在inorder中根节点左边就是leftInorder,根节点右边就是rightInorder。

前序遍历也不难,前序遍历是根左右,preorder第0个数是根节点,后面是左和右,而我们在中序遍历中已经知道了左子树的长度leftLength和右子树的长度rightLength,所有从第1个数往后数leftLength就是左子树的前序遍历leftPreorder,剩下的就是右子树的前序遍历rightPreorder。

然后需要注意的就是,递归的结束,如果左子树的长度小于0就不用递归的创建左子树了,右子树同理,最后返回root。以下是我的代码:

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0){return null;}else{return dfs(preorder, inorder);}}public TreeNode dfs(int[] preorder, int[] inorder){TreeNode root = new TreeNode(preorder[0]);int leftInorderIndex = 0;int rightInorderIndex = 0;int leftPreorderIndex = 0;int rightPreorderIndex = 0;//在中序遍历中找到根节点for(int i=0;i<inorder.length;i++){if(inorder[i] == root.val){leftInorderIndex = i-1;rightInorderIndex = i+1;break;}}//找到左子树长度和右子树长度int leftLength = leftInorderIndex+1;int rightLength = inorder.length - rightInorderIndex;if(leftLength > 0){//创建leftInorderint[] leftInorder = new int[leftLength];for(int i=0;i<leftInorder.length;i++){leftInorder[i] = inorder[i];}//创建leftPreorderint[] leftPreorder = new int[leftLength];int index =1;for(int i=0;i<leftPreorder.length;i++){leftPreorder[i] = preorder[index];index++;}//递归出根节点的左子树root.left = dfs(leftPreorder, leftInorder);}if(rightLength > 0){//创建出rightInorderrightPreorderIndex = leftLength+1;int[] rightInorder = new int[rightLength];int index0= rightInorderIndex;for(int i=0;i<rightInorder.length;i++){rightInorder[i] = inorder[index0];index0++;}//创建出rightPreorderint[] rightPreorder = new int[rightLength];int index1 = rightPreorderIndex;for(int i=0;i<rightPreorder.length;i++){rightPreorder[i] = preorder[index1];index1++;}//递归出根节点的右子树root.right = dfs(rightPreorder, rightInorder);}return root;}
}

看看官方题解做法:

题解的方法一用的也是递归,但是他用了一个HashMap来快速定位根节点,还有就是他没有去创建左右子树的前中遍历序列数组,他直接传前序,中序遍历在inorder中的起始下标和终止下标,因为他们在数组中是连续的,这样全局只需要用这个最大的inorder和preorder就可以,不用花费时间和空间去创建数组,以下是题解方法一代码:

class Solution {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍历中的第一个节点就是根节点int preorder_root = preorder_left;// 在中序遍历中定位根节点int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;// 递归地构造左子树,并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树,并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 构造哈希映射,帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}

题解的第二种方法是迭代,

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || preorder.length == 0) {return null;}TreeNode root = new TreeNode(preorder[0]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.length; i++) {int preorderVal = preorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.left = new TreeNode(preorderVal);stack.push(node.left);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex++;}node.right = new TreeNode(preorderVal);stack.push(node.right);}}return root;}
}
http://www.15wanjia.com/news/18303.html

相关文章:

  • 织梦网站访问量统计代码网络营销的成功案例
  • 服务器做网站用什么环境好太原seo快速排名
  • 网站开发代码h5网站自己推广
  • 网站模版上线需要什么口碑营销成功案例
  • 设计手机网站建设河南网站排名优化
  • 网站被降权的表现北京网站推广排名
  • 中英文网站asp怎么做名风seo软件
  • 营销型网站策划建设分为哪几个层次销售找客户的方法
  • 如何快速做网站排名办公软件速成培训班
  • 做图表好用网站或软件四川百度推广和seo优化
  • 制作自己的网站教程有广告位怎么找广告商
  • 美女图片网站源码商业版本带数据全站生成html_带采集功能资讯门户类网站有哪些
  • 男女做暖暖叉下体视频网站武汉抖音seo搜索
  • 西安西部数码备案网站郑州抖音推广
  • 成都网站制作公司报价星巴克网络营销案例分析
  • 做公司的网站html底部友情链接代码
  • 商品展示网站源码网站推广要点
  • 食品营销型网站百度知道在线
  • dw做的网站如何上传中文域名的网站
  • 中小型网站建设哪家好小程序定制
  • 做鸡人网站杭州推广公司排名
  • 房产网站做那个比较好竞价推广的企业
  • 电子商务网站的重要性做推广的软件有哪些
  • 拉萨做网站公司免费网络项目资源网
  • 用boots做网站成人专业技能培训机构
  • 亚马逊品牌网站要怎么做百度软件中心
  • 网站建设会遇到哪些难题it培训班学出来有用吗
  • 猪八戒网站做推广怎么样seo专员工作内容
  • 网站设计开发建设公司百度指数指的是什么
  • 用凡科帮别人做网站兰州网络优化seo