Construct Binary Tree from Inorder and Postorder Traversal

Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

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

Solution

public class Solution {
    int i; //index of inorder
    int p; //index of postorder

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = inorder.length - 1;
        p = postorder.length - 1;
        return helper(inorder, postorder, null);
    }

    private TreeNode helper(int[] inorder, int[] postorder, TreeNode root) {
        if (p < 0) return null;
        TreeNode node = new TreeNode(postorder[p--]);
        //Create right subtree if right node exists  
        if (inorder[i] != node.val) node.right = helper(inorder, postorder, node);
        i--;
        //Create left subtree if left node exists 
        if (root == null || inorder[i] != root.val) node.left = helper(inorder, postorder, root);
        return node;
    }
}

Analysis