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.

Solution:

This problem can be solved recursively if we notice that the last element of the postorder is the root and all the elements that appear before the root in the inorder belong to the left subbranch and the ones that appear after to the right one.

public class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) 

    {

        return buildTree(inorder, 0, postorder, 0, inorder.length);

    }

    

    private TreeNode buildTree(int[] inorder, int bi, int[] postorder, int bp, int nelements)

    {

        if(nelements<1)

            return null;

        if (nelements==1)

            return new TreeNode(inorder[bi]);

        TreeNode sol = new TreeNode(postorder[bp+nelements-1]);

        for(int i=0; i<nelements; i++)

        {

            if(inorder[bi+i]==sol.val)

            {

                sol.left=buildTree(inorder, bi, postorder, bp, i);

                sol.right=buildTree(inorder, bi+i+1, postorder, bp+i, nelements-i-1);

                break;

            }

        }

        return sol;

    }

}