106. Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
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:
The last one in the post-order sequence must be the root, so the root node of the original binary tree can be known. A very key condition is given in the title that there are no identical elements in the tree.
With this condition, we can also locate in the in-order traversal to find the position of the root node, and split the in-order traversal into the left and right parts according to the position of the root node, and call the original function on it recursively