# Here is my O(n log n) solution. Is there any better solution accepted?

• The idea is:

1. Find root: root must be last postorder element

2. Search for root in inorder array. This point is the middle of two subtrees.

Left subtree inorder elements are to the left of 'middle'. Right subtree elements are to the right of 'middle'
For postorder elements: starting from 0 count to inorder left size. Then inorder right size. Last element (previous root) can be eliminated.

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

if (inorder.length == 0) {
return null;
}
if (inorder.length == 1) {
return new TreeNode(inorder[0]);
}

TreeNode root = findRoot(inorder, postorder);
int middle = findMiddle(inorder, root);

int[] inorderLeft = Arrays.copyOfRange(inorder, 0, middle);
int[] inorderRight = Arrays.copyOfRange(inorder, middle+1, inorder.length);
int[] postOrderLeft = Arrays.copyOfRange(postorder, 0, inorderLeft.length);
int[] postOrderRight = Arrays.copyOfRange(postorder, inorderLeft.length, inorderLeft.length+inorderRight.length);

root.left = buildTree(inorderLeft, postOrderLeft);
root.right = buildTree(inorderRight, postOrderRight);

return root;
}

private TreeNode findRoot(int[] inorder, int [] postorder) {
return new TreeNode(postorder[postorder.length-1]);
}

private int findMiddle(int[] inorder, TreeNode node) {
int middle = -1;
for (int i=0; middle==-1;i++) {
if (inorder[i] == node.val) {
middle = i;
}
}
return middle;
}
``````

}

• First of all, why do you think your code runs in O(n log n)? Your findMiddle function runs in O(n). In the worst case your code runs in O(n^2) - just think of the case where inorder = [1,2,3,...,n] and postorder = [1,2,3,...,n].

There is a O(n) solution which is based on the same observation that you have stated but avoids any explicit partitioning or "findMiddle". Basically the algorithm does the following:

We construct nodes by iterating backwards through the inorder and postorder array.
The main iteration is over the postorder array, creating one node for each value we encounter. We use the inorder array to determine whose child it is.

``````class Solution:
def buildTree(self, inorder, postorder):
if len(inorder) == 0:
return None

postorder_idx = len(postorder)-1
inorder_idx = len(inorder)-1

# not strictly a parent stack
# more of a stack of nodes whose values haven't appeared in
# inorder yet
parent = []

# set initial node
root = TreeNode(postorder[postorder_idx])
postorder_idx -= 1

cur = root
while postorder_idx >= 0:
# if we haven't seen the current value in the inorder array
# then we know that the next node is going to be the right child
# of the current node
while cur.val != inorder[inorder_idx]:
parent.append(cur)
cur.right = TreeNode(postorder[postorder_idx])
postorder_idx -= 1
cur = cur.right

if postorder_idx < 0:
break

inorder_idx -= 1

# the next root belongs to a left subtree
# find the correct subtree it belongs to
while len(parent) > 0 and parent[-1].val == inorder[inorder_idx]:
inorder_idx -= 1
cur = parent.pop()

# finally set the left subtree and continue the reconstruction
# from there
cur.left = TreeNode(postorder[postorder_idx])
postorder_idx -= 1
cur = cur.left

return root``````

• Great! Your solution is iterative. There is another recursive solution which time complexity is O(n). Just changing the findMiddle function to HashMap and finding index will cost O(1). However, the space complexity is O(n).

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