安阳市建设工程领域网站,Asp.net 手机网站制作,福建网站优化建设,响应式网站一般怎么设计给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 题目中是给定两个数组#xff0c;一个是存放这颗树的前序遍历的数组#xff0c;一个是存放这棵树的… 给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 题目中是给定两个数组一个是存放这颗树的前序遍历的数组一个是存放这棵树的中序遍历的数组解这道题的关键我们首先要知道树的前中序遍历分别指的是什么它们两者之间到底存在着什么关系解下来让我们一探究竟
前序遍历 前序遍历的遍历顺序是中左右先遍历自己后遍历自己的左子树最后再遍历自己的右子树由上图已知该树的前序遍历为[3920157]
中序遍历 中序遍历的遍历顺序是左中右先遍历左子树后遍历自己最后再遍历自己的右子树由上图已知该树的中序遍历为[9315207] 观看这两个数组有没有发现什么特别的地方 树是一种天然的递归结构每棵子树也可以称为一棵独立的树根据上图我们不难发现数组中的元素是严格按照中左右的顺序填充的 根据上图我们不难发现数组中的元素是严格按照中左右的顺序填充的
所以我们再来看这两个数组的特点 我们已经得知了这两个数组中的相存的特点接下来就可以撸代码了
我们要通过数组中的元素值得到该元素在数组中的索引为位置所们先要使用Map结构的数据结构去对我们的中序遍历时的数据进行预处理 MapInteger,Integer mapnew HashMap();for(int i0;iinorder.length;i){map.put(inorder[i],i);}
然后开始我们的构建函数dfs前序数组前序开始的位置前序结束的位置中序数组中序开始的位置中序结束的位置 return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
递归时如果出先了开始位置比结束位置还要大的时候这种情况肯定是不满足我们的条件的所以直接抛出null就可以了
if(pStartpEnd||iStartiEnd){return null;}
通过前序遍历数组拿到我们相对根节点然后通过map去查询我们中序数组中我们的相对根节点的索引index因为我们的中序遍历是左中右所以中序遍历中的index-iStart的长度就是我们相对子树的节点的个数 int valpreorder[pStart];TreeNode rootnew TreeNode(val);int sizemap.get(val);int lengthsize-iStart;
最后开始dfs构造左右子树这道题就完成了 // 不包括当前的根结点 前序取不到起点左开右闭 中序取不到终点左闭右开root.leftdfs(preorder,pStart1,pStartlength,inorder,iStart,size-1);// 左子树下一次递归的起点 root.rightdfs(preorder,pStartlength1,pEnd,inorder,size1,iEnd);// 右子树下一次递归的起点
接下来上源码供大家参考 MapInteger,Integer mapnew HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {if(preordernull||inordernull){return null;}for(int i0;iinorder.length;i){map.put(inorder[i],i);}return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode dfs(int[] preorder,int pStart,int pEnd,int[]inorder,int iStart,int iEnd){if(pStartpEnd||iStartiEnd){return null;}int valpreorder[pStart];TreeNode rootnew TreeNode(val);int sizemap.get(val);int lengthsize-iStart;root.leftdfs(preorder,pStart1,pStartlength,inorder,iStart,size-1);root.rightdfs(preorder,pStartlength1,pEnd,inorder,size1,iEnd);return root;}
