[Python] simple stack, explained
Similar to Problem 297: Serialize and Deserialize Binary Tree, but here we do not really need to reconstruct our tree, and using stack is enough. The trick is t
Similar to Problem **297**: Serialize and Deserialize Binary Tree, but here we do not really need to reconstruct our tree, and using stack is enough. The trick is to add elements one by one and when we see `num, #, #`, we replace it with `#`. If we get just one `#` in the end, return `True`, else: `False`. Let us look at the example `9,3,4,#,#,1,#,#,2,#,6,#,#`. Let us go through steps:\n\n1. We add elements until we have `9, 3, 4, #, #`. It means now that `4` is leaf, so let us remove it: we have `9, 3, #`.\n2. Add elements, so we have `9, 3, #, 1, #, #`. We have leaf `1`, remove it: `9, 3, #, #`. Now, we have `3` as leaf as well: remove it: `9, #`.\n3. Add elements `9, #, 2, #, 6, #, #` -> `9, #, 2, #, # -> 9, #, # -> #`.\n\n#### Complexity\nIt is `O(n)` for time and `O(h)` for space, where `h` is the height of our binary tree.\n\n#### Code\n```python\nclass Solution:\n    def isValidSerialization(self, preorder):\n        stack = []\n        for elem in preorder.split(","):\n            stack.append(elem)\n            while len(stack) > 2 and stack[-2:] == ["#"]*2 and stack[-3] != "#":\n                stack.pop(-3)\n                stack.pop(-2)\n            \n        return stack == ["#"]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Stack']