← 전체 회차
a-058-construct-binary-tree-from-preorder-and-inorder-traversal2026-07-04mediumleetcode #105neetcode150

전위 순회와 중위 순회로부터 이진 트리 구성하기

#array#hash-table#divide-and-conquer#tree#binary-tree
↗ leetcode #105 · a-058-construct-binary-tree-from-preorder-and-inorder-traversal
01

문제

· problem
P.a-058-construct-binary-tree-from-preorder-and-inorder-traversal

전위 순회와 중위 순회로부터 이진 트리 구성하기

↗ leetcode #105

정수 배열 두 개가 주어집니다: preorder는 이진 트리의 전위 순회이고, inorder는 같은 트리의 중위 순회입니다. 이 두 배열로부터 이진 트리를 구성하여 반환하세요.

제약
  • · 1 ≤ preorder.length ≤ 3000
  • · inorder.length == preorder.length
  • · -3000 ≤ preorder[i], inorder[i] ≤ 3000
  • · All values in preorder and inorder are unique
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,9,20,15,7]
[9,3,15,20,7]
[3,9,20,null,null,15,7]
example 2input → output
[-1]
[-1]
[-1]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    전위 순회와 중위 순회는 각각 무엇입니까?
  • ☐
    전위 순회에서 첫 번째 원소가 항상 루트가 되는 이유는?
  • ☐
    중위 배열에서 루트의 위치를 찾은 후 그 인덱스를 어떻게 활용합니까?
  • ☐
    좌우 부분트리의 preorder와 inorder 부분배열 길이가 반드시 같아야 하는 이유는?
  • ☐
    전위 순회 배열만으로 원본 트리를 유일하게 복원할 수 있습니까?
  • ☐
    preorder와 inorder가 실제로 같은 트리를 나타내는지 검증해야 합니까?
  • ☐
    배열 슬라이싱으로 인한 공간 복잡도는 O(n)입니까?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 기저 사례: 빈 배열 확인
○
if not preorder or not inorder:
○
if preorder and inorder:
○
if len(preorder) == 0 or len(inorder) == 0:
○
if preorder is None or inorder is None:
step 2· 루트 노드 생성
○
root = TreeNode(preorder[0])
○
root = TreeNode(inorder[0])
○
root = TreeNode(preorder[-1])
○
root = TreeNode((preorder[0] + inorder[0]) // 2)
step 3· 분할점 찾기: 중위에서 루트의 위치
○
mid = inorder.index(preorder[0])
○
mid = preorder.index(root.val)
○
mid = len(inorder) // 2
○
mid = inorder.index(preorder[mid])
step 4· 좌측 부분트리 재귀 구성
○
root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
○
root.left = self.buildTree(preorder[1:mid], inorder[:mid])
○
root.left = self.buildTree(preorder[1:], inorder[:mid])
○
root.left = self.buildTree(preorder[1:mid+1], inorder[:mid+1])
step 5· 우측 부분트리 재귀 구성
○
root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
○
root.right = self.buildTree(preorder[mid:], inorder[mid+1:])
○
root.right = self.buildTree(preorder[mid+1:], inorder[mid:])
○
root.right = self.buildTree(preorder[mid:], inorder[mid:])
step 6· 구성한 트리 반환
○
return root
○
return root.val
○
return None
○
return root.left, root.right
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
3
        if not preorder or not inorder:
4
            return None
5
6
        root = TreeNode(preorder[0])
7
        mid = inorder.index(preorder[0])
8
        root.left = self.buildTree(preorder[1 : mid + 1], inorder[:mid])
9
        root.right = self.buildTree(preorder[mid + 1 :], inorder[mid + 1 :])
10
        return root
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,9,20,15,7]
[9,3,15,20,7]
→
[3,9,20,null,null,15,7]
case 2
[-1]
[-1]
→
[-1]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.