题目链接：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
题目：
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
思路：
递归。
算法：
-
public int search(int nums[], int target) {
-
for (int i = 0; i < nums.length; i++) {
-
if (nums[i] == target)
-
return i;
-
}
-
return -1;
-
}
-
-
public TreeNode buildTree(int[] preorder, int[] inorder) {
-
if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
-
return null;
-
}
-
-
int start = -1, index = -1;
-
for (int i = 0; i < preorder.length; i++) {
-
int tmp = search(inorder, preorder[i]);
-
if (tmp >= 0) {
-
index = tmp;
-
start = i;
-
break;
-
}
-
}
-
TreeNode root = new TreeNode(preorder[start]);
-
if (inorder.length == 1) {
-
return root;
-
}
-
int leftInorder[] = Arrays.copyOfRange(inorder, 0, index);
-
int rightInorder[] = Arrays.copyOfRange(inorder, index + 1, inorder.length);
-
int newpreorder[] = Arrays.copyOfRange(preorder, start + 1, preorder.length);
-
root.left = buildTree(newpreorder, leftInorder);
-
root.right = buildTree(newpreorder, rightInorder);
-
return root;
-
}
【Leetcode】Construct Binary Tree from Preorder and Inorder Traversal
原文：http://blog.csdn.net/yeqiuzs/article/details/51472685
