从前序与中序遍历序列构造二叉树

public class Day26 {

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        Day26 demo = new Day26();
        TreeNode treeNode = demo.buildTree(preorder, inorder);
        System.out.println(treeNode);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int perLen = preorder.length;
        int inLen = inorder.length;
        if (perLen != inLen) {
            throw new RuntimeException("Incorrect input data");
        }
        Map map = new HashMap<>();
        for (int i = 0; i < inLen; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, 0, perLen - 1, map, 0, inLen - 1);
    }

    
    private TreeNode buildTree(int[] preorder, int preLeft, int preRight, Map map, int inLeft, int inRight) {
        // 如果左边界>右边界,则没有节点
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
        
        Integer pIndex = map.get(rootVal);
        
        root.left = buildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);
        
        root.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}