[Leetcode Solution] Construct Binary Tree from Inorder and Postorder Traversal

Analysis

• Inorder traversal is a traversal scheme that first visit the left child node and then visit the parent node and finally visit the right node
• Postorder traversal is visit the parent node and last
• Given inorder traversal sequence and postorder traversal sequence, we can first find out the root node which stored at the end of postorder traversal sequence
• Then according to finding the position of root node in the inorder traversal sequence, we can separate the sequence into two parts which are nodes belonging to left sub tree and right sub tree separately. 
• Have the length of each sub tree, we could also extract their postorder traversal sequence at the postorder traversal sequence of root node
• At this point, we can build the two sub tree recursively and then point the root node child pointers to them.
• The recursion termination condition is when the traversal sequence is empty

Note

Code