문제

풀이

정석이라고 생각한 array 방식

from collections import deque
# 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):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root:
            li = [0, root.val]
            length = 2

            q = deque()
            q.append([1, root]) # [index, node]
            while q:
                parentPointer, parent = q.popleft()
                li.extend([None]*(parentPointer*2+1-length+1))
                length = parentPointer*2+2

                if parent.left:
                    leftPointer = parentPointer *2
                    q.append([leftPointer,parent.left])
                    li[leftPointer] = parent.left.val
                if parent.right:
                    rightPointer = parentPointer *2 +1
                    q.append([rightPointer, parent.right])
                    li[rightPointer] = parent.right.val
            return str(li)[1:-1] 
        else:
            return ""
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data:
            li = list(map(str, data.split(", ")))
            for ind, el in enumerate(li):
                if el != "None":
                    li[ind] = TreeNode(str(el))
                else:
                    li[ind] = None

            for i in range(1, len(li)):
                if li[i]:
                    li[i].left = li[2*i]
                    li[i].right = li[2*i+1]
            if len(li) > 1:
                return li[1]
        else:
            return None
        
        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

자료구조 때 이렇게 하라고 배웠는데..... 메모리 초과

dfs

class Codec:
    def serialize(self, root):
        def recursion(thisNode):
            if thisNode:
                li.append(str(thisNode.val))
                recursion(thisNode.left)
                recursion(thisNode.right)
            else:
                li.append("#")
        
        li = []
        recursion(root)
        return ",".join(li)
    
    def deserialize(self, data):
        global pointer
        pointer = 0 
        li = list(map(str, data.split(",")))
        
        def recursion():
            global pointer
            if li[pointer] == "#":
                pointer += 1
                return None
            node = TreeNode(int(li[pointer]))
            pointer += 1
            node.left = recursion()
            node.right = recursion()
            return node
        return recursion() 

큐 대신 dfs 방식으로 recursion으로 해봤다..
그리고 위에서 메모리 초과가 난건, 엄청나게 많은 None 때문인 듯 했다.
그냥 dfs로 des해서 dfs로 그대로 ser 한다면, none은 자식이 진짜 없을 때 한번만 넣어줘도 된다.

결과

에구 힘드로