[코테연습] 889. Construct Binary Tree from Preorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/?envType=daily-question&envId=2025-02-23

 

📌 문제 다시 정리

• preorder와 postorder 배열이 주어질 때, 이 배열을 기반으로 이진 트리를 구성하는 문제야.
• 노드 값은 중복되지 않는다 → 따라서 항상 유일한 트리를 만들 수 있음.
• preorder는 (루트 → 왼쪽 → 오른쪽) 순서이고,
  postorder는 (왼쪽 → 오른쪽 → 루트) 순서야.

 

✅ Java 코드 한 줄씩 설명

먼저 코드 전체를 보고, 한 줄씩 뜯어보자.

 

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private HashMap<Integer, Integer> postorderIndexMap;
    private int preorderIndex = 0;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        postorderIndexMap = new HashMap<>();

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

        return buildTree(preorder, postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int[] postorder, int left, int right) {
        if (left > right || preorderIndex >= preorder.length) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preorderIndex++]);

        if (left == right) {
            return root;
        }

        int leftSubtreeRootVal = preorder[preorderIndex];
        int leftSubtreeIndex = postorderIndexMap.get(leftSubtreeRootVal);

        root.left = buildTree(preorder, postorder, left, leftSubtreeIndex);
        root.right = buildTree(preorder, postorder, leftSubtreeIndex + 1, right - 1);

        return root;
    }
}

 

1️⃣ TreeNode 클래스 정의

 

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

 

• 이진 트리를 나타내는 노드 클래스를 정의.
• val: 현재 노드의 값.
• left: 왼쪽 자식 노드.
• right: 오른쪽 자식 노드.
• 생성자를 이용해 값을 초기화한다.

 

2️⃣ Solution 클래스의 필드

 

class Solution {
    private HashMap<Integer, Integer> postorderIndexMap;
    private int preorderIndex = 0;

 

 

• postorderIndexMap: 후위 순회에서 노드 값과 인덱스를 매핑해서 저장하는 HashMap.
  • 예를 들어 postorder = [4, 5, 2, 6, 7, 3, 1]이면 {4=0, 5=1, 2=2, 6=3, 7=4, 3=5, 1=6}이 저장됨.
  • 이렇게 하면 O(1)의 시간복잡도로 인덱스를 찾을 수 있음.
• preorderIndex: 전위 순회 배열에서 현재 탐색 중인 인덱스.
  • 처음에는 0, 즉 preorder[0]부터 탐색을 시작함.

3️⃣ constructFromPrePost 함수

 

public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
    postorderIndexMap = new HashMap<>();

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

    return buildTree(preorder, postorder, 0, postorder.length - 1);
}

 

 

🔹 하는 일

1. postorderIndexMap을 채운다 → 후위 순회 배열의 각 값과 인덱스를 저장.
2. buildTree(preorder, postorder, 0, postorder.length - 1) 호출하여 트리를 만든다.

 

4️⃣ buildTree 함수 (트리 재귀 생성)

 

private TreeNode buildTree(int[] preorder, int[] postorder, int left, int right) {

preorder와 postorder를 사용해, left부터 right 범위의 서브트리를 만드는 재귀 함수.

 

5️⃣ 기저 조건 (Base Case)

if (left > right || preorderIndex >= preorder.length) {
    return null;
}

 

• left > right: 탐색 범위를 벗어나면 null 반환.
• preorderIndex >= preorder.length: preorder를 다 탐색했으면 null 반환.

6️⃣ 현재 노드 생성

TreeNode root = new TreeNode(preorder[preorderIndex++]);

 

 

• preorder[preorderIndex] 값을 사용하여 현재 노드 생성.
• preorderIndex++: 다음 호출에서 preorder의 다음 값 사용.

7️⃣ 단일 노드인 경우 바로 반환

if (left == right) {
    return root;
}

 

서브트리에 더 이상 자식이 없으면 현재 노드 반환.

 

8️⃣ 왼쪽 서브트리 루트 찾기

int leftSubtreeRootVal = preorder[preorderIndex];
int leftSubtreeIndex = postorderIndexMap.get(leftSubtreeRootVal);

 

• preorder[preorderIndex]: 왼쪽 서브트리의 루트 값.
• postorderIndexMap.get(leftSubtreeRootVal): 후위 순회에서 왼쪽 서브트리의 마지막 노드 위치 찾기.

9️⃣ 왼쪽 서브트리 재귀 호출

root.left = buildTree(preorder, postorder, left, leftSubtreeIndex);

 

 

left ~ leftSubtreeIndex 범위에서 왼쪽 서브트리 생성

 

🔟 오른쪽 서브트리 재귀 호출

 

root.right = buildTree(preorder, postorder, leftSubtreeIndex + 1, right - 1);

 

leftSubtreeIndex + 1 ~ right-1 범위에서 오른쪽 서브트리 생성.

 

> python

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        postorder_index_map = { val : idx for idx, val in enumerate(postorder)}
        self.preorder_index = 0

        def buildTree(left: int, right : int) -> Optional[TreeNode] :
            if left > right or self.preorder_index >= len(preorder) :
                return None
            
            root = TreeNode(preorder[self.preorder_index])
            self.preorder_index += 1

            if left == right :
                return root

            left_subtree_root_val = preorder[self.preorder_index]
            left_subtree_index = postorder_index_map[left_subtree_root_val]

            root.left = buildTree(left, left_subtree_index)
            root.right = buildTree(left_subtree_index+1, right-1)

            return root
        
        return buildTree(0, len(postorder) - 1)