Leet Code 889. Construct Binary Tree from Preorder and Postorder Traversal

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

package pep.Day69;

public class Construction_BinaryTree_From_PostOrder_and_PreOrder {

    public static void main(String[] args) {

        int[] pre = {1, 2, 3, 4};
        int[] post = {3, 4, 2, 1};

        Construction_BinaryTree_From_PostOrder_and_PreOrder x = new Construction_BinaryTree_From_PostOrder_and_PreOrder();
        x.constructFromPrePost(pre, post);
    }

    class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode() {

        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode constructFromPrePost(int[] preOrder, int[] postOrder) {
        TreeNode x = constructFromPrePost1(preOrder, 0, preOrder.length - 1, postOrder, 0, postOrder.length - 1);
        return x;
    }

    public TreeNode constructFromPrePost1(int[] preOrder, int preStart, int preEnd, int[] postOrder, int postStart, int postEnd) {

        if (preStart > preEnd)
            return null;

        TreeNode root = new TreeNode(postOrder[postEnd]);
        // base case: jisme ek hi node hogi eg. pre=[1], post[1]
        if (preStart == preEnd) {
            return root;
        }

        // find root element in PostOrder from PreOrder
        int i = findRoot_In_PostOrder(postOrder, preOrder[preStart + 1]);

        int leftCount = i - postStart + 1;

        root.left = constructFromPrePost1(preOrder, preStart + 1, preStart + leftCount, postOrder, postStart, i);
        root.right = constructFromPrePost1(preOrder, preStart + leftCount + 1, preEnd, postOrder, i + 1, postEnd - 1);

        return root;
    }

    public int findRoot_In_PostOrder(int[] postOrder, int rootLeftData) {
        for (int i = 0; i < postOrder.length; i++) {
            if (postOrder[i] == rootLeftData)
                return i;
        }
        return -1;
    }
}