Python solution with detailed explanation


  • 0
    G

    Solution

    Serialize and Deserialize Binary Tree https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

    Preorder & DFS

    • Serialize using pre-order and represent null by "#"
    • Deserialize by traversing the serialized tree and using recursion. O(N).
    class Codec:
        def preorder_serialize(self, root, result):
            if root == None:
                result.append("#")
            else:
                result.append(str(root.val))
                self.preorder_serialize(root.left, result)
                self.preorder_serialize(root.right, result)        
            return
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            result = []
            self.preorder_serialize(root, result)
            return ",".join(result)
    
        def pre_order_deserialize(self, pre_order):
            if pre_order[self.idx] == "#":
                return None
            else:
                node = TreeNode(pre_order[self.idx])
                self.idx += 1
                node.left =  self.pre_order_deserialize(pre_order)
                self.idx += 1
                node.right =  self.pre_order_deserialize(pre_order)
                return node
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            pre_order = data.split(",")
            self.idx = 0
            return self.pre_order_deserialize(pre_order)
    

    BFS

    • Serialize the tree level by level using BFS. Typical BFS method to handle a binary tree. Use string n to represent null values. The string of the binary tree in the example will be "1 2 3 n n 4 5 n n n n ".
    • Deserialize using queue and BFS variant. Assign left and right child for each not-null node, and add the not-null children to the queue, waiting to be handled later.
    • Example, load the queue with TreeNode(1) and maintain a variable i which points to index location 1 in the serialized string.
    • Now when we pop the queue and get Node(1), we check the index 1 and 2 for its left and right children. If any of them are non-null, we create them and attach them to Node(1) and then insert them back into the queue.
    • https://discuss.leetcode.com/topic/31264/short-and-straight-forward-bfs-java-code-with-a-queue
    from collections import deque
    class Codec:
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            q, result = deque(), []
            q.append(root)
            while len(q):
                x = q.popleft()
                if x == None:
                    result.append("#")
                else:
                    result.append(str(x.val))
                    q.append(x.left)
                    q.append(x.right)
            return ",".join(result)
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            data, q, idx = data.split(","), deque(), 0
            if data[0] == "#":
                return None
            root = TreeNode(data[0])
            q.append(root)
            while len(q):
                x = q.popleft()
                x.left = TreeNode(data[idx+1]) if data[idx+1] != "#" else None
                x.right = TreeNode(data[idx+2]) if data[idx+2] != "#" else None
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
                idx += 2
            return root
    

Log in to reply
 

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