python serialization by pre-order traversal + deserializaion by queue


  • 0
    Z
    import json
    from collections import deque
    
    class Codec:
    
        def serialize(self, root):
            height_vals = {}
            def serialize_helper(tree, height, height_vals):
                height_vals.setdefault(height, [])
                height_vals[height].append(tree.val if tree else None)
                if tree:
                    serialize_helper(tree.left, height+1, height_vals)
                    serialize_helper(tree.right, height+1, height_vals)
            serialize_helper(root, 0, height_vals)    
            nodes = []
            for height, ls in height_vals.items():
                nodes += ls
            while nodes and not nodes[-1] != None:
                nodes.pop()
            return json.dumps(nodes)
            
    
        def deserialize(self, data):
            vals = json.loads(data)
            if not vals:
                return None
            root = TreeNode(vals[0])
            vals = vals[1:]
            queue = deque([(root, 0), (root,1)])
            for tree in vals:
                if tree != None:
                    tree = TreeNode(tree)
                    queue.append((tree, 0))
                    queue.append((tree,1))
                parent, isRight = queue.popleft()
                if isRight:
                    parent.right = tree
                else:
                    parent.left = tree
            return root

Log in to reply
 

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