成都大型网站维护公司,商务网站建设与维护 课件,网站策划书网站需求分析,论坛建设免费思路 根据两个顺序构造一个唯一的二叉树#xff0c;以 后先序数组的第一个元素为切割点#xff0c;先切中序数组#xff0c;根据中序数组#xff0c;反过来在切先序数组。一层一层切下去#xff0c;每次先序数组第一个元素就是节点元素。
第一步#xff1a;如果数组大小…思路 根据两个顺序构造一个唯一的二叉树以 后先序数组的第一个元素为切割点先切中序数组根据中序数组反过来在切先序数组。一层一层切下去每次先序数组第一个元素就是节点元素。
第一步如果数组大小为零的话说明是空节点了。
第二步如果不为空那么取先序数组第一个元素作为节点元素。
第三步找到先序数组第一个元素在中序数组的位置作为切割点
第四步切割中序数组切成中序左数组和中序右数组 顺序别搞反了一定是先切中序数组
第五步切割先序数组切成先序左数组和先序右数组
第六步递归处理左区间和右区间
难点就是如何切割以及边界值找不好很容易乱套。
首先要切割中序数组为什么先切割中序数组呢
切割点在先序数组的第一个元素就是用这个元素来切割中序数组的所以必要先切割中序数组。
中序数组相对比较好切找到切割点先序数组的第一个元素在中序数组的位置然后切割如下代码中我坚持左闭右开的原则
int rootIndexmap.get(preorder[preBegin]);//找到前序遍历第一个元素在中序中的位置
接下来切割先序数组。
首先后序数组的第一个元素指定不能要了这是切割点 也是 当前二叉树中间节点的元素已经用了。
先序数组的切割点怎么找
先序数组没有明确的切割元素来进行左右切割不像中序数组有明确的切割点切割点左右分开就可以了。
此时有一个很重的点就是中序数组大小一定是和先序数组的大小相同的这是必然。
中序数组我们都切成了左中序数组和右中序数组了那么先序数组就可以按照左中序数组的大小来切割切成左先序数组和右先序数组。
/*** 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 {MapInteger,Integer map;public TreeNode buildTree(int[] preorder, int[] inorder) {mapnew HashMap();for(int i0;iinorder.length;i){map.put(inorder[i],i);}return findNode(preorder,0,preorder.length,inorder,0,inorder.length);}public TreeNode findNode(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){if(preBeginpreEnd||inBegininEnd){//没有元素返回空return null;}int rootIndexmap.get(preorder[preBegin]);//找到前序遍历第一个元素在中序中的位置TreeNode rootnew TreeNode(inorder[rootIndex]);//构造结点int lenOfLeftrootIndex-inBegin;//保存中序左子树个数root.leftfindNode(preorder,preBegin1,preBeginlenOfLeft1,inorder,inBegin,rootIndex);root.rightfindNode(preorder,preBeginlenOfLeft1,preEnd,inorder,rootIndex1,inEnd);return root;}
}
