algorithm - 使用左/右括号序列化和反序列化树

Question

这里的树有 n 个节点（不是二叉树！）

我试图实现以下的想法

     1       (1((2)(3)(4)))
   /  \  \
  2    3  4
(2)  (3)  (4)

我的初始算法起草如下。序列化函数是在每次调用时返回(根子(节点。))反序列化函数是从括号中构造根及其子节点

有人可以看到为什么实施不正确吗？

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: Node
        :rtype: str
        """
        if not root: return ''

        if not root.children: return '(' + str(root.val) + ')'

        res = "("
        for child in root.children:
            res += self.serialize(child)
        res += ')'  # ((2)(3)(4))
        return '(' + str(root.val) + res + ')' # (1((2)(3)(4)))

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: Node
        """
        #       ^
        # 0 1 2 3 ...
        # ( 1 ( ( 2 )(3) ) )
        if not data: return None
        val = data[1]
        root = Node(int(val))
        root.children = []
        left = 0
        start = 3 # choose 3 as shown above(skip all parenthesis until seeing the children)

        for i in range(3, len(data) - 2): #skip last parentheses for the same reason
            if data[i] == '(': left += 1
            if data[i] == ')':
                left -= 1
                if left == 0:
                    child = self.deserialize(data[start:i + 1])
                    root.children.append(child)
                    start = i + 1

        return root

标签： algorithm