LeetCode--105.从前序和中序遍历序列构造二叉树（二叉树）

题目描述给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]示例 2:输入: preorder [-1], inorder [-1] 输出: [-1]提示:1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历序列inorder保证为二叉树的中序遍历序列代码/** * 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; * } * } */classSolution{MapInteger,IntegermapnewHashMap();publicTreeNodebuildTree(int[]preorder,int[]inorder){if(preorder.length0)returnnull;for(inti0;iinorder.length;i){map.put(inorder[i],i);}returnbuildHepler(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}publicTreeNodebuildHepler(int[]preorder,intpreStart,intpreEnd,int[]inorder,intinStart,intinEnd){// 终止递归条件if(preStartpreEnd||inStartinEnd)returnnull;// 取出先序遍历第一个 在中序遍历中找到他的位置TreeNoderootnewTreeNode(preorder[preStart]);intindexmap.get(preorder[preStart]);// 记录左边长度intleftLengthindex-inStart;root.leftbuildHepler(preorder,preStart1,preStartleftLength,inorder,inStart,inStartleftLength);root.rightbuildHepler(preorder,preStart1leftLength,preEnd,inorder,index1,inEnd);returnroot;}}