Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

29%

Accepted

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

Have you met this question in a real interview? 

Yes

Example

Given inorder [1,2,3] and postorder [1,3,2], return a tree:

  2
 / \
1   3

Note

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

public class Solution {

    /**

     *@param inorder : A list of integers that inorder traversal of a tree

     *@param postorder : A list of integers that postorder traversal of a tree

     *@return : Root of a tree

     */

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

        // write your code here

        return building(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);

    }

    

    private TreeNode building(int[] inorder, int iS, int iE, int[] postorder, int pS, int pE){

        if(iS > iE || pS > pE){

            return null;

        }

        TreeNode root = new TreeNode(postorder[pE]);

        int idx = 0;

        for(int i = iS; i <= iE; i++){

            if(inorder[i] == postorder[pE]){

                idx = i;

                break;

            }

        }

        root.left = building(inorder, iS, idx-1, postorder, pS, pS+(idx-iS-1));

        root.right = building(inorder, idx+1, iE, postorder, pS+idx-iS, pE - 1);

        return root;

        

    }

    

    

}