# A bottom up solution.

• This question can be solved the same as the preorder-inorder one by just reversing the postorder array, but pay a little attention, now you need to construct right child first instead of left child in the previous question. But this is still top-down recursive method. For a tree problem, you can always think the other way. So I tried a bottom-up solution. The advantage of postorder, is that, when you create a new node, both its children should be ready, so you just need to find which ones are the children of current node. I use two maps to keep the created subtrees. If you find a subtree who has a child just next to the current node in the inorder array then it will be the child of the current node.

`````` public TreeNode buildTree(int[] inorder, int[] postorder) {

if (inorder == null || postorder == null) return null;

if (inorder.length==0 || postorder.length==0) return null;

if (inorder.length != postorder.length) return null;

Map<Integer,TreeNodeWithRange> startMap = new HashMap<>();

Map<Integer,TreeNodeWithRange> endMap = new HashMap<>();

Map<Integer,Integer> inorderMap = new HashMap<>();

for (int i=0; i<inorder.length; i++) {
inorderMap.put(inorder[i],i);
}

TreeNode result = null;
for (int i=0; i<postorder.length; i++) {

TreeNode node = new TreeNode(postorder[i]);

int inorderIdx = inorderMap.get(postorder[i]);

TreeNodeWithRange tr = new TreeNodeWithRange();

tr.node = node;

tr.start = inorderIdx;

tr.end = inorderIdx;

TreeNodeWithRange left = endMap.get(inorderIdx-1);

if (left!=null) {
tr.node.left = left.node;
tr.start = left.start;
endMap.remove(left.end);
startMap.remove(left.start);
}

TreeNodeWithRange right = startMap.get(inorderIdx+1);

if(right!=null) {
tr.node.right = right.node;
tr.end = right.end;
startMap.remove(right.start);
endMap.remove(right.end);
}

startMap.put(tr.start,tr);
endMap.put(tr.end,tr);

if (i==postorder.length-1) {
result = node;
}

}

return result;

}

private static class TreeNodeWithRange {

TreeNode node;
int start;
int end;
}``````

• This post is deleted!

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.