Leet Code 105. Construct Binary Tree from Preorder and Inorder Traversal

Example 1:

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

package pep.Day69;

public class Construction_BinaryTree_From_PreOrder_and_InOrder {

    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[] preorder, int[] inorder) {
        return preIn(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode preIn(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {

        // base case
        if (preStart > preEnd) {
            return null;
        }

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

        int lcount = i - inStart;

        root.left = preIn(preOrder, preStart + 1, preStart + lcount, inOrder, inStart, i - 1);
        root.right = preIn(preOrder, preStart + lcount + 1, preEnd, inOrder, i + 1, inEnd);

        return root;
    }

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