Leetcode 297. Serialize and Deserialize Binary Tree

Problem

Leetcode 297 - Serialize and Deserialize Binary Tree

Example:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Input: root = []
Output: []

Approach

We can use DFS to serialize. If the corresponding node has no value (None), then we can append a value ‘N’ to indicate that node is going to be None.

For deserialize part, we can also use DFS to create the nodes, and if we encounter ‘N’, then we can return None

Here is the Python code for the solution:

class Codec:
    def serialize(self, root):
        res = []

        def dfs(root):
            if not root:
                res.append('N')
                return
            
            res.append(str(root.val))
            dfs(root.left)
            dfs(root.right)

        return ','.join(res) 

    def deserialize(self, data):
        val = data.split(',')
        self.index = 0

        def dfs():
            if val[self.index] == 'N':
                self.index += 1
                return None
            
            root = TreeNode(int(val[self.index]))
            self.index += 1
            root.left = dfs()
            root.right = dfs()
            return root
        
        return dfs()    

Time Complexity and Space Complexity

Time Complexity: $O(n)$ for all operations

Space Complexity: $O(n)$ for all operations