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