449: Time 91.2%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nFor the serialize function:\n\n1. If the given root is None, return an em
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFor the serialize function:\n\n1. If the given root is None, return an empty string.\n2. Create an empty stack and push the root node to it.\n3. Create an empty string called serialized.\n4. While the stack is not empty, pop a node from the stack.\n5. If the node is None, append "$," to the serialized string.\n6. Otherwise, append the node\'s value followed by "," to the serialized string.\n7. Push the node\'s right child to the stack (if it exists).\n8. Push the node\'s left child to the stack (if it exists).\n9. Return the serialized string without the last comma.\n\nFor the deserialize function:\n\n1. If the given data string is empty, return None.\n2. Split the data string by comma and create a deque called queue from the resulting list.\n3. Call the _deserialize function with queue as the argument and return its result.\n\nFor the _deserialize function:\n\n1. Pop the leftmost value from the queue and store it in a variable called value.\n2. If value is "$", return None.\n3. Create a new TreeNode with the integer value of value.\n4. Set the node\'s left child to the result of calling _deserialize recursively with queue.\n5. Set the node\'s right child to the result of calling _deserialize recursively with queue.\n6. Return the node.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Codec:\n    def serialize(self, root: Optional[TreeNode]) -> str:\n        """Encodes a tree to a single string."""\n        if not root:\n            return ""\n        stack = [root]\n        serialized = ""\n        while stack:\n            node = stack.pop()\n            if not node:\n                serialized += "$,"\n            else:\n                serialized += str(node.val) + ","\n                stack.append(node.right)\n                stack.append(node.left)\n        return serialized[:-1]\n\n    def deserialize(self, data: str) -> Optional[TreeNode]:\n        """Decodes your encoded data to tree."""\n        if not data:\n            return None\n        values = data.split(",")\n        queue = deque(values)\n        return self._deserialize(queue)\n\n    def _deserialize(self, queue: Deque[str]) -> Optional[TreeNode]:\n        value = queue.popleft()\n        if value == "$":\n            return None\n        node = TreeNode(int(value))\n        node.left = self._deserialize(queue)\n        node.right = self._deserialize(queue)\n        return node\n```
['String', 'Tree', 'Depth-First Search', 'Python', 'Python3']