前面学习过根据中序遍历和后序遍历结果构造二叉树，今天是类似的给定一颗树的中序遍历和前序序遍历两个结果数组，构造成一颗二叉树。
题目介绍
题目就简单介绍下，给定两个数组，一个是中序遍历后的输出结果，一个是前序遍历的输出结果。需要根据两个数组构造二叉树。
实现思路
和之前的中序以及后序的解题思路不一样的是，今天主要换中方式来实现。先简单的介绍下思路吧，后续再补充解题过程图纸。
之前的实现是不断的递归裁剪数组，这次的方式的通过下标加长度的方式来递归构造树。每次通过两个数组定位左右子树的起始下标，以及子树的节点数量。这样就可以递归的构造树了。
实现代码
代码逻辑是对的，不过实现还需再次优化下。
public class SolutionConsturtFromPreorderAndInorder {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, inorder, 0, 0, preorder.length);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int prelo, int inlo, int num) {
if (num <= 0) {
return null;
}
TreeNode node = new TreeNode(preorder[prelo]);
if (num > 1) {
int rootVal = preorder[prelo]; //子树根节点值
int i = inlo;
for (; i < (inlo + num) && inorder[i] != rootVal; i++) ;
int lnum = i - inlo;
int rnum = inlo + num - i;
node.left = buildTree(preorder, inorder, prelo, inlo, lnum);
node.right = buildTree(preorder, inorder, prelo + lnum + 1, inlo + lnum + 1, rnum);
}
return node;
}
}
算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms
