Leetcode: 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.

Understand the problem:
The problem asks for constructing a binary tree given inorder and postorder traversal of the tree. The problem is similar to the last post. So we can still use the same idea to construct a tree recursively.

Solution:
Since the last element of the post-order traversal must be the parent. So the value can partition the inorder array into two parts, the first part must be its left subtree, while the second part must be its right subtree. So now we partition the problem into two smaller problems, and we can recursively partition the list again until each subtree has only one element. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0)
            return null;
        
        int len = inorder.length;
        return buildTree(inorder, 0, len - 1, postorder, 0, len - 1);
    }
    
    private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int poStart, int poEnd) {
        if (inStart > inEnd) return null;
        
        int rootVal = postorder[poEnd];
        int rootIdx = 0;
        
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIdx = i;
                break;
            }
        }
        
        TreeNode root = new TreeNode(rootVal);
        int len = rootIdx - inStart;
        
        root.left = buildTree(inorder, inStart, rootIdx - 1, postorder, poStart, poStart + len - 1);
        root.right = buildTree(inorder, rootIdx + 1, inEnd, postorder, poStart + len, poEnd - 1);
        
        return root;
    }
}

FOLLOW-UP
Given a preorder and postorder of a tree, can we construct the binary tree?
The answer is NO. We must need an inorder traversal to construct the tree. That is because 
the order of the inorder traversal is left child -> parent -> right child. So given a parent node, we can easily partition the list into left subtree and right subtree. But given only preorder and postorder traversal, there is no way to partition the list. 

Summary:
In this post, we learned how to construct a binary tree from its inorder and postorder traversal. The key idea is using recursion. It is the key to solve this kind of questions.