[LeetCode 105] Construct Binary Tree from Preorder and Inorder (Java)

🚀 문제 분석

• 목표: 이진 트리의 전위 순회(Preorder)와 중위 순회(Inorder) 결과가 주어졌을 때, 원래의 이진 트리를 구축합니다.
• 핵심: 각 순회 방식이 가진 고유한 특성을 결합하여 '루트 노드'와 '서브트리의 경계'를 찾아내는 것이 포인트입니다.
  • Preorder (Root -> L -> R): 배열의 첫 번째 요소가 항상 루트입니다.
  • Inorder (L -> Root -> R): 루트를 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리로 나뉩니다.

💡 해결 전략: 분할 정복과 해시맵 최적화

전위 순회에서 루트를 하나씩 꺼내고, 중위 순회에서 그 루트의 위치를 찾아 범위를 쪼개나가는 방식을 사용합니다.

1. 위치 정보 사전 등록: 중위 순회 배열에서 특정 값의 인덱스를 매번 찾으면 $O(N)$이 걸리므로, HashMap에 미리 저장하여 $O(1)$로 조회할 수 있게 최적화합니다.
2. 루트 결정 (Preorder 활용): preorder[k]는 현재 서브트리의 루트입니다. 결정 후 k를 증가시켜 다음 루트 후보를 가리킵니다.
3. 경계 분할 (Inorder 활용): 해시맵에서 찾은 루트의 위치(mid)를 기준으로:
   • [low, mid - 1] 범위는 왼쪽 자식 노드들이 됩니다.
   • [mid + 1, high] 범위는 오른쪽 자식 노드들이 됩니다.
4. 재귀적 구축: 이 과정을 반복하여 리프 노드까지 트리를 완성해 나갑니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_105 {

    // 중위 순회 값의 인덱스를 빠르게 찾기 위한 맵
    private Map<Integer, Integer> valueToIndex = new HashMap<>();
    // 전위 순회 배열에서 루트를 순차적으로 꺼내기 위한 포인터
    private int k = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 1. 중위 순회 값과 인덱스를 맵에 등록 (O(N))
        for (int i = 0; i < inorder.length; i++) {
            valueToIndex.put(inorder[i], i);
        }
        return organize(preorder, 0, inorder.length - 1);
    }

    private TreeNode organize(int[] preorder, int low, int high) {
        // 기저 사례: 더 이상 나눌 범위가 없으면 null
        if (low > high) {
            return null;
        }

        // 2. 전위 순회의 현재 순서(k) 값을 루트로 생성
        TreeNode root = new TreeNode(preorder[k++]);
        
        // 3. 중위 순회에서 해당 루트의 위치를 찾음
        int mid = valueToIndex.get(root.val);
        
        // 4. 루트를 기준으로 좌/우 범위를 나누어 재귀적으로 자식 노드 생성
        // 반드시 왼쪽 서브트리를 먼저 구축해야 함 (Preorder가 Root -> L -> R 순서이므로)
        root.left = organize(preorder, low, mid - 1);
        root.right = organize(preorder, mid + 1, high);

        return root;
    }
}

🧐 기술적 고찰

• 탐색 최적화: 매 재귀마다 inorder 배열을 선형 탐색했다면 $O(N^2)$이 되었겠지만, HashMap을 활용해 전체 로직을 $O(N)$으로 최적화했습니다.
• 순서의 중요성: preorder 순서에 맞춰 k를 증가시키기 때문에, 재귀 호출 시 반드시 root.left를 먼저 호출해야 합니다. 이는 전위 순회의 구조적 특징을 정확히 이해하고 있어야 구현 가능한 디테일입니다.
• 분할 정복의 정석: 큰 문제를 루트를 기준으로 작은 두 개의 서브트리 문제로 쪼개어 해결하는 전형적인 분할 정복 알고리즘의 사례입니다.