serialize_and_deserialize_binary_tree

View Source

 1from utils import TreeNode
 2from collections import defaultdict, deque
 3from itertools import chain
 4
 5
 6# @leet start
 7class Codec:
 8    """
 9    This class serializes and deserializes a binary tree.
10    """
11
12    def serialize(self, root):
13        """
14        The serialize function takes a treenode and returns a string.
15        It does a bfs (for a level-order traversal) of the nodes and then
16        puts them in a defaultdict.
17        Finally, since nulls are allowed, the last level will be all nulls.
18        That is removed from the dict with serialized.popitem()
19        and then joined with '#' to send over the wire.
20        """
21        if not root:
22            return ""
23        serialized = defaultdict(list)
24        q = deque()
25        q.append((root, 0))
26
27        while q:
28            node, level = q.popleft()
29            if not node:
30                serialized[level].append(None)
31                continue
32            else:
33                serialized[level].append(node.val)
34            q.append((node.left, level + 1))
35            q.append((node.right, level + 1))
36
37        serialized.popitem()
38        return "#".join(map(lambda x: str(x), list(chain(*serialized.values()))))
39
40    def deserialize(self, data):
41        """
42        This function takes the string representation, splits it for every #
43        and then returns the root node that represents that tree.
44
45        It takes the first node of that list and creates a root, and then
46        for each node in the queue, it takes the next left and right nodes
47        and moves through the queue, adding nodes back onto the queue, for each
48        remaining item in the string.
49        """
50        if not data:
51            return None
52        l = data.split("#")
53        root = TreeNode(int(l[0]))
54        q = deque()
55        q.append(root)
56        i = 1
57        while q and i < len(l):
58            node = q.popleft()
59            if l[i] != str(None):
60                left = TreeNode(int(l[i]))
61                node.left = left
62                q.append(left)
63            i += 1
64            if l[i] != str(None):
65                right = TreeNode(int(l[i]))
66                node.right = right
67                q.append(right)
68            i += 1
69        return root
70
71
72# Your Codec object will be instantiated and called as such:
73# ser = Codec()
74# deser = Codec()
75# ans = deser.deserialize(ser.serialize(root))
76# @leet end
77
78
79def test():
80    assert 2 + 2 == 4

class Codec: View Source

 8class Codec:
 9    """
10    This class serializes and deserializes a binary tree.
11    """
12
13    def serialize(self, root):
14        """
15        The serialize function takes a treenode and returns a string.
16        It does a bfs (for a level-order traversal) of the nodes and then
17        puts them in a defaultdict.
18        Finally, since nulls are allowed, the last level will be all nulls.
19        That is removed from the dict with serialized.popitem()
20        and then joined with '#' to send over the wire.
21        """
22        if not root:
23            return ""
24        serialized = defaultdict(list)
25        q = deque()
26        q.append((root, 0))
27
28        while q:
29            node, level = q.popleft()
30            if not node:
31                serialized[level].append(None)
32                continue
33            else:
34                serialized[level].append(node.val)
35            q.append((node.left, level + 1))
36            q.append((node.right, level + 1))
37
38        serialized.popitem()
39        return "#".join(map(lambda x: str(x), list(chain(*serialized.values()))))
40
41    def deserialize(self, data):
42        """
43        This function takes the string representation, splits it for every #
44        and then returns the root node that represents that tree.
45
46        It takes the first node of that list and creates a root, and then
47        for each node in the queue, it takes the next left and right nodes
48        and moves through the queue, adding nodes back onto the queue, for each
49        remaining item in the string.
50        """
51        if not data:
52            return None
53        l = data.split("#")
54        root = TreeNode(int(l[0]))
55        q = deque()
56        q.append(root)
57        i = 1
58        while q and i < len(l):
59            node = q.popleft()
60            if l[i] != str(None):
61                left = TreeNode(int(l[i]))
62                node.left = left
63                q.append(left)
64            i += 1
65            if l[i] != str(None):
66                right = TreeNode(int(l[i]))
67                node.right = right
68                q.append(right)
69            i += 1
70        return root

This class serializes and deserializes a binary tree.

def serialize(self, root): View Source

13    def serialize(self, root):
14        """
15        The serialize function takes a treenode and returns a string.
16        It does a bfs (for a level-order traversal) of the nodes and then
17        puts them in a defaultdict.
18        Finally, since nulls are allowed, the last level will be all nulls.
19        That is removed from the dict with serialized.popitem()
20        and then joined with '#' to send over the wire.
21        """
22        if not root:
23            return ""
24        serialized = defaultdict(list)
25        q = deque()
26        q.append((root, 0))
27
28        while q:
29            node, level = q.popleft()
30            if not node:
31                serialized[level].append(None)
32                continue
33            else:
34                serialized[level].append(node.val)
35            q.append((node.left, level + 1))
36            q.append((node.right, level + 1))
37
38        serialized.popitem()
39        return "#".join(map(lambda x: str(x), list(chain(*serialized.values()))))

The serialize function takes a treenode and returns a string. It does a bfs (for a level-order traversal) of the nodes and then puts them in a defaultdict. Finally, since nulls are allowed, the last level will be all nulls. That is removed from the dict with serialized.popitem() and then joined with '#' to send over the wire.

def deserialize(self, data): View Source

41    def deserialize(self, data):
42        """
43        This function takes the string representation, splits it for every #
44        and then returns the root node that represents that tree.
45
46        It takes the first node of that list and creates a root, and then
47        for each node in the queue, it takes the next left and right nodes
48        and moves through the queue, adding nodes back onto the queue, for each
49        remaining item in the string.
50        """
51        if not data:
52            return None
53        l = data.split("#")
54        root = TreeNode(int(l[0]))
55        q = deque()
56        q.append(root)
57        i = 1
58        while q and i < len(l):
59            node = q.popleft()
60            if l[i] != str(None):
61                left = TreeNode(int(l[i]))
62                node.left = left
63                q.append(left)
64            i += 1
65            if l[i] != str(None):
66                right = TreeNode(int(l[i]))
67                node.right = right
68                q.append(right)
69            i += 1
70        return root

This function takes the string representation, splits it for every # and then returns the root node that represents that tree.

It takes the first node of that list and creates a root, and then for each node in the queue, it takes the next left and right nodes and moves through the queue, adding nodes back onto the queue, for each remaining item in the string.

def test(): View Source

80def test():
81    assert 2 + 2 == 4