Leetcode-Solutions/449_Serialize_and_Deserialize_BST.py at master · shivammaniharsahu/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def inord(self, root, arr):
        if not root:
            return
        self.inord(root.left,arr)
        arr.append(str(root.val))
        self.inord(root.right,arr)

    def postord(self, root, arr):
        if not root:
            return
        self.postord(root.left,arr)
        self.postord(root.right,arr)
        arr.append(str(root.val))


    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        inorder = []
        postorder = []

        self.inord(root, inorder)
        self.postord(root, postorder)

        string = ",".join(inorder) + '$' + ','.join(postorder)
        print(string)
        return string

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if data == "$":
            return None
        inorder, postorder = data.split('$')
        inorder = [int(i) for i in inorder.split(',')]
        postorder = [int(i) for i in postorder.split(',')]

        return self.buildTree(inorder,postorder)


    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        inorderDict = {}
        n = len(inorder)
        for i in range(n):
            inorderDict[inorder[i]] = i

        start = 0
        end = n-1

        self.head = None

        self.build(inorder, postorder, inorderDict, None, start, end, False, n-1)

        return self.head


    def build(self, inorder, postorder, inorderDict, head, start, end, left, rootIndex ):
        if start > end:
            return rootIndex
        nodeVal = postorder[rootIndex]
        index = inorderDict[nodeVal]
        rootIndex -= 1
        if head == None:
            head = TreeNode(nodeVal)
            self.head = head
        elif left:
            head.left = TreeNode(nodeVal)
            head = head.left
        else:
            head.right = TreeNode(nodeVal)
            head = head.right

        rootIndex = self.build(inorder, postorder, inorderDict, head, index+1, end, False, rootIndex)
        rootIndex = self.build(inorder, postorder, inorderDict, head, start, index-1, True, rootIndex)

        return rootIndex

# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans