A Python Solution Using json


  • 0

    The solution below used json & dict to serialize/deserialize a binary tree.

    The tree node can be converted to a dict including 3 fields:

    v : value 
    l : left-child
    r : right-child

    Sample:

    [1,null,2,3]

       1
        \
         2
        /
       3
    
    {"r": {"l": {"v": 3}, "v": 2}, "v": 1} 

    Python code as follows:

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    import json
    class Codec:
    
        def serialize(self, root):
            """Encodes a tree to a single string.
            
            :type root: TreeNode
            :rtype: str
            """
            if not root:
                return 'null'
            nodes = collections.deque([root])
            maps = collections.deque([{'v' : root.val}])
            tree = maps[0]
            while nodes:
                frontNode = nodes.popleft()
                frontMap = maps.popleft()
                if frontNode.left:
                    frontMap['l'] = {'v' : frontNode.left.val}
                    nodes.append(frontNode.left)
                    maps.append(frontMap['l'])
                if frontNode.right:
                    frontMap['r'] = {'v' : frontNode.right.val}
                    nodes.append(frontNode.right)
                    maps.append(frontMap['r'])
            return json.dumps(tree)
    
        def deserialize(self, data):
            """Decodes your encoded data to tree.
            
            :type data: str
            :rtype: TreeNode
            """
            tree = json.loads(data)
            if not tree:
                return None
            root = TreeNode(tree['v'])
            maps = collections.deque([tree])
            nodes = collections.deque([root])
            while nodes:
                frontNode = nodes.popleft()
                frontMap = maps.popleft()
                left, right = frontMap.get('l'), frontMap.get('r')
                if left:
                    frontNode.left = TreeNode(left['v'])
                    maps.append(left)
                    nodes.append(frontNode.left)
                if right:
                    frontNode.right = TreeNode(right['v'])
                    maps.append(right)
                    nodes.append(frontNode.right)
            return root
            
    
    # Your Codec object will be instantiated and called as such:
    # codec = Codec()
    # codec.deserialize(codec.serialize(root))
    

    ref: http://bookshadow.com/weblog/2015/10/26/leetcode-serialize-and-deserialize-binary-tree/


Log in to reply
 

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