O(n) && O(n) for Solution 2
/*
solution 2 is faster because of HashMap
The basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(postorder.length - 1, 0, inorder.length - 1, inorder, postorder);
}
private TreeNode helper(int postEnd, int inStart, int inEnd, int[] inorder, int[] postorder) {
if(postEnd < 0 || inStart > inEnd)
return null;
TreeNode root = new TreeNode(postorder[postEnd]);
int inRoot = 0;
for(int i = inStart; i <= inEnd; i++) {
if(root.val == inorder[i])
inRoot = i;
}
int numsRight = inEnd - inRoot;
root.left = helper(postEnd - numsRight - 1, inStart, inRoot - 1, inorder, postorder);
root.right = helper(postEnd - 1, inRoot + 1, inEnd, inorder, postorder);
return root;
}
}
/*
比第一种多了map
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length)
return null;
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < inorder.length; i++)
map.put(inorder[i], i);
return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, map);
}
public TreeNode helper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, HashMap<Integer,Integer> map){
if(inStart > inEnd || postStart > postEnd)
return null;
int inRoot = map.get(postorder[postEnd]);
TreeNode root = new TreeNode(postorder[postEnd]);
int len = inRoot - inStart;
root.left = helper(inorder, inStart, inRoot - 1, postorder, postStart, postStart + len - 1, map);
root.right = helper(inorder, inStart + len + 1, inEnd, postorder, postStart + len, postEnd - 1, map);
return root;
}
}