106. 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.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]Return the following binary tree:
3
/ \
9 20
/ \
15 7Taken from here.
To solve this problem we need to understand, what is inorder and what is postorder traversal of tree. Let me remind you:
inordertraversal is when you visitleft, root, right, whereleftis left subtree,rootis root node andrightis right subtree.postordertraversal is when you visitleft, right, root.
We can see that in postorder traverasl root will be in the end, so we take this element and we need to find it in inorder array.
Then we need to call function recursively on the left subtree and right subtree. It is easier said that done, so let us introduce function helper(post_beg, post_end, in_beg, in_end), which has 4 parameters:
post_begandpost_endare indices in originalpostorderarray of current window. Note, that we use python notation, sopost_endpoints to one element after the end.in_begandin_endare indices in originalinorderarray of current window. We again use python notation, wherein_endpoints to one element after the end.
Then what we need to do is to find indices of left part and right part. First of all, evaluate ind = dic[postorder[post_end-1]], where we create dic = {elem: it for it, elem in enumerate(inorder)} for fast access to elements. Now, look at the next two images:
On the first one 1, 2, 3, 4 in circles are equal to post_beg, post_beg + ind - in_beg, in_beg, ind. Why? 1 should point to beginning of left in postorder, so it is equal to post_beg. 2 should point to one element after the end of left, so we need to know the length of left, we can find it from inorder array, it is ind - in_beg. So, finally, point 2 is equal to post_beg + ind - in_beg. Point 3 should point to start of left in inorder array, that is in_beg and point 4 should point to element after the end of left in inorder array, that is ind.
On the second one 1, 2, 3, 4 in circles are equal to post_end - in_end + ind, post_end - 1, ind + 1, in_end. The logic is similar as for left parts, but here we look into right arrays.
Complexity: Time complexity is O(n), because we traverse each element only once and we have O(1) complexity to find element in dic. Space complexity is also O(n), because we keep additional dic with this size.
class Solution:
def buildTree(self, inorder, postorder):
def helper(post_beg, post_end, in_beg, in_end):
if post_end - post_beg <= 0: return None
ind = dic[postorder[post_end-1]]
root = TreeNode(inorder[ind])
root.left = helper(post_beg, post_beg + ind - in_beg, in_beg, ind)
root.right = helper(post_end - in_end + ind, post_end - 1, ind + 1, in_end)
return root
dic = {elem: it for it, elem in enumerate(inorder)}
return helper(0, len(postorder), 0, len(inorder))Last updated
Was this helpful?