Construct Binary Tree from Preorder and Inorder

1package pkg5leetcode.blind75;2 3/*4 * Construct Binary Tree from Preorder and Inorder | LC 1055 * APPROACH: Root from pre[0]; split inorder by root index recursively.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC105ConstructBinaryTreeFromPreorderAndInorder {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static TreeNode buildTree(int[] preorder, int[] inorder) {20        Map<Integer, Integer> idx = new HashMap<>();21        for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);22        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, idx);23    }24 25    static TreeNode build(int[] pre, int pl, int pr, int[] in, int il, int ir, Map<Integer, Integer> idx) {26        if (pl > pr) return null;27        int rootVal = pre[pl];28        TreeNode root = new TreeNode(rootVal);29        int mid = idx.get(rootVal);30        int leftSize = mid - il;31        root.left = build(pre, pl + 1, pl + leftSize, in, il, mid - 1, idx);32        root.right = build(pre, pl + leftSize + 1, pr, in, mid + 1, ir, idx);33        return root;34    }35 36    public static void main(String[] args) {37        TreeNode t = buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});38        check(t.val == 3 && t.left.val == 9 && t.right.left.val == 15, "case1");39        TreeNode t2 = buildTree(new int[]{-1}, new int[]{-1});40        check(t2.val == -1 && t2.left == null, "case2");41        System.out.println("all tests passed");42    }43 44    static void check(boolean cond, String name) {45        if (!cond) throw new AssertionError("FAILED: " + name);46        System.out.println("  PASS " + name);47    }48}