# LeetCode Hard 297. Serialize and Deserialize Binary Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

二分木を文字列に変換し，その文字列を二分木に戻すメソッドを書けという問題です．

どのような変換の仕方でも良いようですが，メソッド間で使える変数を使ってその状態を保持しないようにしろとのことです．

LeetCodeの二分木の表現に合わせてみることにします

解法

• serialize
  • BFSをして，親→左→右という順番で文字列にします
  • Noneの場合はnullとします．(文字列で表現)
• deserialize
  • 文字列をsplitを使うことで分割します．
  • そして，要素の最初から見ていきます．
  • 要素がnullのときは無視して，そうでない場合は左，右と代入していきます．

計算量

ノードの数を$N$，木の深さを$H$とします．

• 時間計算量
  • ノードの全てを走査することがあるので$O(N)$
• 空間計算量
  • ノード全てを格納することがあるので$O(N)$

Python

# 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 not root:
            return ""
        q = collections.deque([root])
        res = []
        while q:
            cur = q.popleft()
            if cur:
                q.append(cur.left)
                q.append(cur.right)
            res.append(str(cur.val) if cur else "null")
        return ",".join(res)
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        nodes = data.split(",")
        root = TreeNode(int(nodes[0]))
        q = collections.deque([root])
        index = 1
        while q:
            cur = q.popleft()
            if nodes[index] != "null":
                cur.left = TreeNode(int(nodes[index]))
                q.append(cur.left)
            index += 1
            
            if nodes[index] != "null":
                cur.right = TreeNode(int(nodes[index]))
                q.append(cur.right)
            index += 1
        return root
    
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))