[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 풀이

✔️ 오늘의 리트코드 공부 기록 – Construct Binary Tree

---

문제 요약 (Construct Binary Tree from Preorder and Inorder Traversal)

Preorder 순회 배열과 Inorder 순회 배열이 주어진다. 이 두 배열을 이용해 원래의 이진 트리를 복원하라.
단, 모든 노드는 중복되지 않는다.

문제링크:
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

---

🤔 처음 떠올린 아이디어

처음에는 이런 생각이 들었다.

트리를 어떻게 배열 두 개로 다시 만들지?

배열을 잘라야 하나?
왼쪽, 오른쪽을 어떻게 구분하지?

막막했지만, 순회 방식의 정의를 다시 떠올려봤다.

---

💡 첫 번째 깨달음: Preorder의 첫 값은 항상 루트

Preorder는

• Root → Left → Right

즉, preorder[0] = 전체 트리의 루트

이걸 깨닫는 순간 문제는 이렇게 바뀐다.

👉 “루트는 이미 알고 있다.”

---

💡 두 번째 깨달음: Inorder는 트리를 정확히 나눈다

Inorder는

• Left → Root → Right

루트를 inorder에서 찾으면 이렇게 나뉜다.

[Left Subtree]  Root  [Right Subtree]

즉, Inorder는 트리의 구조 정보를 제공한다.

---

🧠 사고 전환: 전체 트리가 아니라 “서브트리” 문제

“전체 트리를 한 번에 만들려고 하지 말고,
현재 서브트리 하나만 만들자.”

그러면 로직은 단순해진다.

1. preorder에서 루트 하나 뽑기
2. inorder에서 그 위치 찾기
3. 왼쪽 구간 재귀
4. 오른쪽 구간 재귀

이게 그대로 반복된다.

---

📌 핵심 포인트

👉 배열을 자르지 않는다
👉 inorder의 인덱스 범위만 넘긴다

그리고 preorder는 전역 index 하나로 관리한다.
이렇게 하면 자연스럽게 Root → Left → Right 순서가 유지된다.

---

코드 (Java)

class Solution {

    private Map<Integer, Integer> inorderMap = new HashMap<>();
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int inStart, int inEnd) {

        if (inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inorderMap.get(rootVal);

        root.left = build(preorder, inStart, rootIndex - 1);
        root.right = build(preorder, rootIndex + 1, inEnd);

        return root;
    }
}

📈 시간/공간 복잡도

• 시간: 각 노드를 한 번씩 방문 → O(N)
• 공간: 재귀 호출 스택 → O(H) (최악 O(N))

🔍 왜 HashMap이 필요한가?

만약 매번 inorder에서 루트를 찾기 위해 선형 탐색을 하면 O(N) × N번 호출 = O(N²)

따라서 value → index 매핑을 미리 만들어두는 것이 핵심이다.

---

📝 이번 문제에서 얻은 깨달음

• 트리 복원 문제는 값 비교 문제가 아니다 → 구조 분리 문제다
• 순회 문제가 나오면 먼저 생각할 것 → “루트는 어디서 결정되는가?”
• 재귀는 문제를 줄이는 도구다 → 전체 트리가 아니라 현재 서브트리만 생각하자