(Tree, Medium) Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

핵심 아이디어는
전위 순회를 베이스로 루트를 선택하고, 그 루트를 기준으로 왼쪽 서브트리, 오른쪽 서브트리 순으로 순회하는 것

그래도 혼자 생각할 때 아이디어가 안 떠올라서 GPT 참고함
기본적으로는 preOrder로 순회하는데, 이것을 루트로 삼아 left, right를 서브트리를 구함

결론적으로
preOrder의 경우 배열 순서대로 루트가 되며,
각각의 inOrder는 이 루트값을 기준으로 왼쪽/오른쪽이 나뉘는 것.

이것을 구현하기 위해서는 preOrder에 대한 포인터와 inOrder에 대한 포인터는 따로 관리가 되어야 함.

이 때 GPT는 inOrder의 포인터를 직관적이고 쉽게 다루기 위해 별도 해시맵에 담는다.
이것으로 pre (root)를 찾고 그 값을 기반으로 inOrder 배열에서 그 값이 어느 인덱스에 존재하는 지 얻을 수 있다.

class Solution {
    private int preIdx; // preorder에서 현재 루트 위치(전역 포인터)
    private int[] preorder;
    private int[] inorder;
    private java.util.Map<Integer, Integer> inIndex; // 값 -> inorder 인덱스

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        this.preIdx = 0;

        // inorder 값 -> 인덱스 맵 구성 (O(N))
        inIndex = new java.util.HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inIndex.put(inorder[i], i);
        }

        // inorder 구간 [inL, inR] (포함 범위)에서 트리 구성
        return build(0, inorder.length - 1);
    }

    private TreeNode build(int inL, int inR) {
        // 중위 구간이 비었으면 서브트리 없음
        if (inL > inR) return null;

        // 전위에서 현재 루트를 꺼냄
        int rootVal = preorder[preIdx++];
        TreeNode root = new TreeNode(rootVal);

        // 중위에서 루트 위치 찾기
        int mid = inIndex.get(rootVal);

        // 왼쪽: [inL, mid - 1], 오른쪽: [mid + 1, inR]
        root.left = build(inL, mid - 1);
        root.right = build(mid + 1, inR);

        return root;
    }
}