根據二叉樹的前序數組和中序序遍歷數組生成二叉樹

題目：給定二叉樹的前序遍歷和中序遍歷，生成二叉樹。

Example:

前序遍歷數組：preArr[]:{1，2，4，5，3，6，7}

中序遍歷數組：inArr[]：{4，2，5，1，6，3，7}

生成的二叉樹如下圖：

解題思路：

由二叉樹的前序變量性質可知：preArr[0] 是數組的根節點，有根據二叉樹的中序遍歷的性質可知，{4，2，5}是二叉樹的左子樹,{6,3,7}在右子樹上，重復執行該操作就構造出了二叉樹

public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode root = new TreeNode(pre[0]);//前序的第一個數定為根
int len = pre.length;
//當只有一個數的時候
if (len == 1) {
root.left = null;
root.right = null;
return root;
}
//找到中序中的根位置
int rootval = root.val;
int i;
for (i = 0; i < len; i++) {
if (rootval == in[i])
break;
}
//創建左子樹
if (i > 0) {
int[] pr = new int[i];
int[] ino = new int[i];

for (int j = 0; j < i; j++) {
pr[j] = pre[j + 1];
}
for (int j = 0; j < i; j++) {
ino[j] = in[j];
}
root.left = reConstructBinaryTree(pr, ino);
} else {
root.left = null;
}
//創建右子樹
if (len - i - 1 > 0) {
int[] pr = new int[len - i - 1];
int[] ino = new int[len - i - 1];
for (int j = i + 1; j < len; j++) {
ino[j - i - 1] = in[j];
pr[j - i - 1] = pre[j];
}
root.right = reConstructBinaryTree(pr, ino);
} else {
root.right = null;
}
return root;
}

public static void main(String[] args) {
int[] preArr = {1, 2, 4, 5, 3, 6, 7};
int[] inArr = {4, 2, 5, 1, 6, 3, 7};
Solution s = new Solution();
TreeNode root = s.reConstructBinaryTree(preArr, inArr);
s.postOrder(root);
}