[Python3] image water flowing through the tree
Approach 1 - outlet \nThink of the tree as water pipeline. Initially, there is one inlet toward the root. By adding an inner node, an extra outlet is introduced
Approach 1 - outlet \nThink of the tree as water pipeline. Initially, there is one inlet toward the root. By adding an inner node, an extra outlet is introduced in a binary tree (+1). By adding a leaf node, a possible outlet is blocked (-1). \n\nSo the problem becomes to check if inlet and outlet are balancing. Given there was an initialy inlet (which requires 1 outlet) and each inner node introduces an extra outlet, `1 + inner` leaf nodes are required for the balance. Of course, end result alone is not enough. One also need to check the intermediate state. Namely, at any state before the end, one would require positive number of outlets. \n\n```\nclass Solution:\n    def isValidSerialization(self, preorder: str) -> bool:\n        outlet = 1\n        for x in preorder.split(","): \n            if outlet == 0: return False #intermediate \n            outlet += 1 if x != "#" else -1\n        return outlet == 0  #end result \n```\n\nApproach 2 - reconstruction \nAlternatively, one could somewhat reconstruct the tree via a stack. \n```\nclass Solution:\n    def isValidSerialization(self, preorder: str) -> bool:\n        stack = []\n        for n in preorder.split(","):\n            stack.append(n)\n            while stack[-2:] == ["#", "#"]: \n                stack.pop()\n                stack.pop()\n                if not stack: return False \n                stack[-1] = "#"\n        return stack == ["#"]\n```
['Python3']