题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注：你可以假设树中没有重复的元素。
题解
示例数组：
preorder: [3, 9, 20, 15, 7]
inorder: [9, 3, 15, 20, 7]
结果：
使用递归进行构建，算法如下：
1、将前序数组的第一个值构建根节点
Root
；
2、分割
inorder
数组，分割点为根节点，在示例中以3为节点分割，不包含3，具体分割为
inorder_left
和
inorder_right
；
3、分割
preorder
数组，去除第一个元素，截取到
inorder_left.length
长度的数组作为
preorder_left
，剩下的作为
preorder_right
；
4、递归求解，将
Root.left
指向
inorder_left
和
preorder_left
构建的数根；将
Root.right
指向
inorder_right
和
preorder_right
构建的数根；
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 边界情况判断
if(preorder.length == 0) {
return null;
}
// 初始化根节点
TreeNode N = new TreeNode(preorder[0]);
// 计算分割中序遍历数组的坐标
int k = 0;
for (int i =