Leet Code 106. Construct Binary Tree from Inorder and Postorder Traversal

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

package pep.Day69;

public class Construction_BinaryTree_From_PostOrder_and_InOrder {

    public static void main(String[] args) {
        int[] in = {9, 3, 15, 20, 7};
        int[] post = {9, 15, 7, 20, 3};
        Construction_BinaryTree_From_PostOrder_and_InOrder x = new Construction_BinaryTree_From_PostOrder_and_InOrder();
        x.buildTree(post, in);
    }

    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 buildTree(int[] inOrder, int[] postOrder) {
        TreeNode x = postIn(postOrder, 0, postOrder.length - 1, inOrder, 0, inOrder.length - 1);
        return x;
    }

    public TreeNode postIn(int[] postOrder, int postStart, int postEnd, int[] inOrder, int inStart, int inEnd) {
        // base case
        if (inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postOrder[postEnd]);
        // find root element in InOrder from postOrder
        int i = findRoot_In_InOrder(inOrder, root.val);

        int lcount = i - inStart;

        root.left = postIn(postOrder, postStart, postStart + lcount - 1, inOrder, inStart, i - 1);
        root.right = postIn(postOrder, postStart + lcount, postEnd - 1, inOrder, i + 1, inEnd);

        return root;
    }

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