[1스4코2파] #158. LeetCode pattern 297. Serialize and Deserialize Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (158차)
[4코1파] 2023.01.13~ (150일차)
[1스4코1파] 2023.04.12~ (61일차)
[1스4코2파] 2023.05.03 ~ (40일차)

Today :

2023.06.09 [158일차]

297. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

문제 설명

이진 트리를 직렬화(Serialize)하고 다시 역직렬화(Deserialize) 하는 클래스를 구현한다.

Serialize 메소드로 이진 트리를 문자열 형태로 저장하고, deserialize 메소드로 저장한 문자열을 다시 이진 트리로 변환 한다.

문제 풀이 방법

dfs를 이용해서 serialized (직렬화) 할 때 pre-order로 순회하면서 원소들을 리스트에 넣고 해당 리스트를 문자열로 리턴한다.

deserialized(역직렬화) 시에는 위에서 직렬화 형식으로 변환한 문자열을 다시 리스트 형식으로 변환한 뒤, pre-order 방향으로 노드를 왼쪽, 오른쪽 붙이면서 최종 노드로 리턴한다.

내 코드

# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        ans = []

        def dfs(node):
            if not node:
                ans.append('N')
                return

            ans.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return ','.join(ans)

        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        vals = data.split(',')
        self.i = 0

        def dfs():
            if vals[self.i] == 'N':
                self.i +=1
                return None
            
            node = TreeNode(int(vals[self.i]))
            self.i +=1

            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

증빙

여담

원래는 bfs 로 해보려고 했는데 잘 안되서 dfs로 푼 솔루션으로 이해 완