Python solution using level order traversal


  • 1
    S
    class Codec:
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            result = []
            if not root:
                return result
            #Level order
            queue=collections.deque([root])
            while queue:
                root = queue.pop()
                result.append("#")
                if root:
                    result.append(str(root.val))
                    queue.appendleft(root.left)
                    queue.appendleft(root.right)
            return "".join(result[1:])       
    
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            index = 0
            if not data:
                return None
            data = data.split("#")
            newRoot = TreeNode(data[0])
            queue=collections.deque([newRoot]) 
            index = 1 
            while index < len(data):
                curNode = queue.pop()
                if data[index]:
                    curNode.left = TreeNode(data[index])
                    queue.appendleft(curNode.left)
                index += 1
                if data[index]:
                    curNode.right = TreeNode(data[index])
                    queue.appendleft(curNode.right)
                index += 1
            return newRoot
            
           
            
    
    # Your Codec object will be instantiated and called as such:
    # codec = Codec()
    # codec.deserialize(codec.serialize(root))

Log in to reply
 

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