1
class Codec:
2
    def serialize(self, root: Optional[TreeNode]) -> str:
3
        """Encodes a tree to a single string."""
4
        if not root:
5
            return ""
6
        res = []
7

8
        def dfs(node):
9
            res.append(str(node.val))
10
            if node.left:
11
                dfs(node.left)
12
            if node.right:
13
                dfs(node.right)
14

15
        dfs(root)
16
        return ",".join(res)
17

18
    def deserialize(self, data: str) -> Optional[TreeNode]:
19
        """Decodes your encoded data to tree."""
20
        if len(data) == 0:
21
            return []
22
        splitdata = data.split(",")
23
        preorder = []
24
        for item in splitdata:
25
            preorder.append(int(item))
26
        inorder = sorted(preorder)
27
        hash_map = {}
28
        for i in range(len(inorder)):
29
            hash_map[inorder[i]] = i
30

31
        def helper(preorder, pstart, pend, inorder, istart, iend):
32
            if pstart > pend:
33
                return None
34
            elif pstart == pend:
35
                return TreeNode(preorder[pstart])
36

37
            root = TreeNode(preorder[pstart])
38

39
            rootindex = hash_map[preorder[pstart]]
40

41
            numleft = rootindex - istart
42

43
            root.left = helper(
44
                preorder, pstart + 1, pstart + numleft, inorder, istart, rootindex - 1
45
            )
46
            root.right = helper(
47
                preorder, pstart + numleft + 1, pend, inorder, rootindex + 1, iend
48
            )
49

50
            return root
51

52
        return helper(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)