Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
通过树的中序序列和前序序列来构建一棵树。
例如：一棵树的前序序列是1-2-3，中序序列有5种可能，分别是1-2-3、2-1-3、1-3-2、2-3-1、3-2-1。不同的中序序列对应着不同的树的结构，这几棵树分别是[1,null,2,null,3]/[1,2,3]/[1,null,2,3]/[1,2,null,null,3]/[1,2,null,3]。
那么如何通过前序和中序序列来构建树呢？
我们知道：
1.前序序列是先visit根节点，然后visit左子树，最后visit右子树。
2.中序序列是先visit左子树，然后visit根节点，最后visit右子树。
因此，前序序列的第一个节点是根节点。我们在中序序列中找到根节点的位置，那么中序序列中根节点前面的节点就是根节点左子树中的节点，根节点后面的节点就是根节点右子树的节点。在上面的例子中，比如前序：1-2-3，中序2-1-3。由前序知道，1是根节点，在中序序列中找到1的位置，1前面的数是2，因此2是1的左子树，1的后面是3，因此3是1的右子树。所以对应是树为[1,2,3]。
知道了如何构建树，对应的代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0 || inorder.length==0) return null; TreeNode root = new TreeNode(preorder[0]);
int i;
for(i=0; i<inorder.length; i++){ //找到根节点在中序序列中的位置
if(inorder[i] == preorder[0]) break;
}
int[] left, right, npreorder;
if(i>0){
left = new int[i]; //左子树中的节点
System.arraycopy(inorder, 0, left, 0, left.length);
}else left = new int[0];
if(inorder.length - i -1 > 0){ //右子树中的节点
right = new int[inorder.length - i -1];
System.arraycopy(inorder, i+1, right, 0, right.length);
}else right = new int[0]; npreorder = new int[preorder.length - 1];//删除根节点
System.arraycopy(preorder, 1, npreorder, 0, npreorder.length);
root.left = buildTree(npreorder, left); //构建左子树
npreorder = new int[preorder.length - left.length - 1];//删除左子树中节点
System.arraycopy(preorder, 1 + left.length, npreorder, 0, npreorder.length);
root.right = buildTree(npreorder, right);//构建右子树
return root;
}
}