Leetcode 105：从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
public static TreeNode buildTree(int[] preorder, int[] inorder) {map= new HashMap<>(); // 方便根据数值查找位置for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置map.put(inorder[i], i);}return traversal(preorder,0,preorder.length, inorder,0,inorder.length); // 前闭后开}//递归public static TreeNode traversal(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){if(preBegin>=preEnd || inBegin>=inEnd){return null;}int rootValue=preorder[preBegin];TreeNode root=new TreeNode(rootValue); //创建根节点int rootIndex=map.get(rootValue); //根节点在中序遍历中的位置int leftInLen=rootIndex-inBegin; //计算左子树的长度//构造左子树int leftPreBegin=preBegin+1; //左子树的前序遍历起点int leftPreEnd=preBegin+leftInLen+1; //左子树的前序遍历终点int leftInBegin=inBegin; //左子树的中序遍历起点int leftInEnd= rootIndex; //左子树中序遍历终点root.left=traversal(preorder,leftPreBegin,leftPreEnd,inorder,leftInBegin,leftInEnd);//构造右子树preBegin=preBegin+leftInLen+1; //右子树的前序遍历起点preEnd=preEnd; //右子树的前序遍历终点inBegin=rootIndex+1; //右子树的中序遍历起点inEnd= inEnd; //右子树中序遍历终点root.right=traversal(preorder,preBegin,preEnd,inorder,inBegin,inEnd);return root;}