[Leetcode] Construct Binary Tree from Inorder and Postorder Traversal

Problem 

Given in-order and postorder traversal of a tree, construct the binary tree.

Given preorder and in-order traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Algorithm 

Observation 1. In the preorder traversal of a tree, the root of the tree is the head of the array. 

Observation 2. In the in-order traversal of a tree, the left subtree lies to the left of the root, and the right subtree lies to the right of the root. 

Observation 3. In the postorder traversal of a tree, the root of the tree is the tail of the array. 

Given in-order and postorder traversal of a tree. First, the root of the tree can be found at the end of the postorder traversal. Since all nodes are different, we can find the position of the root in the in-order array. The root divides the in-order array into root's left and right subtrees. Once we know the length of the subtree, we can also divide the postorder traversal array into two halves. After determining the in-order and postorder of subtrees,  we can recursively construct the subtrees and append them to the root. 

Code