a-060-serialize-and-deserialize-binary-tree2026-07-06hardleetcode #297neetcode150

이진 트리의 직렬화와 역직렬화

#string#tree#depth-first-search#breadth-first-search#design#binary-tree

↗ leetcode #297 · a-060-serialize-and-deserialize-binary-tree

문제

· problem

P.a-060-serialize-and-deserialize-binary-tree

이진 트리의 직렬화와 역직렬화

직렬화는 데이터 구조나 객체를 비트 수열로 변환하여 파일이나 메모리 버퍼에 저장하거나 네트워크 연결을 통해 전송한 후, 같은 또는 다른 컴퓨터 환경에서 재구성할 수 있도록 하는 과정입니다. 이진 트리를 직렬화하고 역직렬화하는 알고리즘을 설계하세요. 직렬화/역직렬화 알고리즘이 어떻게 작동하는지에 대한 제한은 없습니다. 이진 트리를 문자열로 직렬화할 수 있고, 이 문자열을 원래의 트리 구조로 역직렬화할 수 있도록 하면 됩니다. 참고: 입출력 형식은 LeetCode가 이진 트리를 직렬화하는 방식과 동일합니다. 이 형식을 반드시 따를 필요는 없으므로, 창의적으로 다양한 접근 방식을 시도해 보세요.

제약

· 0 ≤ number of nodes ≤ 10^4
· -1000 ≤ node.val ≤ 1000

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[1,2,3,null,null,4,5]

[1,2,3,null,null,4,5]

example 2input → output

[]

[]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
직렬화된 문자열의 형식에 제한이 있나요?
☐
null 노드를 어떻게 표현해야 하나요?
☐
트리 순회의 어떤 순서를 사용해야 하나요?
☐
노드의 값이 음수일 수 있나요?
☐
공트리(빈 트리)는 어떻게 처리하나요?
☐
순환 구조(cycle)가 있는 그래프도 처리할 수 있나요?
☐
직렬화된 문자열이 반드시 사람이 읽을 수 있어야 하나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 직렬화 초기화: 결과 리스트

○

res = ""

○

res = []  # Initialize with root value

step 2· 기본 사례: null 노드 표현│ 중첩

○

if not node: return

○

if node is None: res.append(0)

step 3· 재귀 사례: 현재 노드 값 저장│ 중첩

○

dfs(node.left); res.append(str(node.val)); dfs(node.right)

○

res.append(str(node.val)); dfs(node.right); dfs(node.left)

step 4· 전위 순회: 좌우 자식 재귀│ 중첩

○

dfs(node.right); dfs(node.left)

○

if node.left: dfs(node.left); if node.right: dfs(node.right)

step 5· 직렬화 마무리: 컴마로 결합

○

return res

○

return '|'.join(res)

step 6· 역직렬화 초기화: 문자열 분할

○

vals = list(data)

○

vals = data.split('N')

step 7· 재귀적 재구성: 값 팝과 노드 생성│ 중첩

○

val = vals.pop(); if val == 'N': return None; node = TreeNode(int(val)); node.right = dfs(); node.left = dfs(); return node

○

val = vals.pop(0); if val != 'N': node = TreeNode(int(val)); node.left = dfs(); node.right = dfs(); return node

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Codec:

    def serialize(self, root):

        res = []

        def dfs(node):

            if not node:

                res.append("N")

                return

            res.append(str(node.val))

            dfs(node.left)

            dfs(node.right)

        dfs(root)

        return ",".join(res)

    def deserialize(self, data):

        vals = data.split(",")

        def dfs():

            val = vals.pop(0)

            if val == "N":

                return None

            node = TreeNode(val=int(val))

            node.left = dfs()

            node.right = dfs()

            return node

        return dfs()

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[1,2,3,null,null,4,5]

→

[1,2,3,null,null,4,5]

case 2

[]

→

[]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.