leetcode hard : Serialize and Deserialize Binary Tree

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

Serialize and Deserialize Binary Tree - LeetCode

 

노드 개수가 최대 10000개로 O(N^2)까지는 Accept해주는 문제고

정답이 있다기보단 자신만의 창의력을 발휘해서 푸는 문제다.

class 이름도 Codec이네. 재밌는문제다. 이건 솔루션 안보고 직접 풀어보고 싶네.

 

이 문제는 평가요소가 두 가지가 있을수있을거같다.

1. 얼마나 빠르게 serialize/deserialize하는지

2. 얼마나 압축률이 좋은지

 

나는 어디다 포커스를 둘까?

2번에 포커스를 둘까?

serialize하는거 자체가 기억장치에 저장하기 위한 목적이 있는거니까..

 

아 근데 이거.. python이 좀 불리하다.

파이썬은 string이 immutable이라서 concat할때마다 메모리 할당 & 복사가 계속일어난다..;;

dict로 만들어서 str(딕셔너리)로 한번에 serialize하고 직접 파싱하면 될거같긴한데(eval로 파싱이 가능하다) 그럼 built-in function을 쓰는거라 영 기분이 좋지 않다.

근데 built in function을 안쓰면서 스트링 복사 최소화하는 방법이 잘 떠오르지 않는다.

모르겠다 그냥 built in 써야지

 

# 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
        """
        node_map = {'root' : id(root)}

        def dfs(node):
            if not node: return
            val = node.val
            left = id(node.left) if node.left else 0
            right = id(node.right) if node.right else 0
            node_map[id(node)] = (val, left, right)
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)

        return str(node_map)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        node_map = eval(data)

        def parse_node(_id):
            if _id == 0 : return None
            tup = node_map[_id]
            node = TreeNode()
            node.val = tup[0]
            node.left = parse_node(tup[1])
            node.right = parse_node(tup[2])
            return node
        
        if node_map['root'] not in node_map:
            return None
        
        root = parse_node(node_map['root'])
        return root

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

ㅋㅋ 어림도 없지 엄청나게 처참한 결과 딱!!

 

다른사람 솔루션을 보니까 traversal 한 순서대로 string을 만들고 그대로 파싱한다.

class Codec:

    def serialize(self, root):
        def doit(node):
            if node:
                vals.append(str(node.val))
                doit(node.left)
                doit(node.right)
            else:
                vals.append('#')
        vals = []
        doit(root)
        return ' '.join(vals)

    def deserialize(self, data):
        def doit():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = doit()
            node.right = doit()
            return node
        vals = iter(data.split())
        return doit()