Preorder only solution in Python

  • 0

    By the definition of BST, when we serialize it into a preorder string. Root.val will always at the head of string. Right substree will start at j which subjects to data[j] > data[0]. Then construct left and right subtree recursively easily.

    class Codec:
        def serialize(self, root):
            """Encodes a tree to a single string.
            :type root: TreeNode
            :rtype: str
            if not root:
                return ''
            return '#'.join([str(root.val), self.serialize(root.left), self.serialize(root.right)])
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            :type data: str
            :rtype: TreeNode
            return self._deserialize([int(n) for n in data.split('#') if n])
        def _deserialize(self, data):
            if not data:
                return None
            root = TreeNode(data[0])
            j = 1
            while j < len(data):
                if data[j] > data[0]:
                j += 1
            root.left = self._deserialize(data[1:j])
            root.right = self._deserialize(data[j:])
            return root

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.