As the tree grows, the number of open leaves dynamically changes. we just need to count these leaves.
when a new node comes, whether empty or not, it has to attach to some current leaf position, and as the preorder list gets exhausted, there must be no leave positions open (all sealed by '#', thus not open).
we start with 1 leaf position for the root to attach on, and then when there comes a non-empty node, the total open leave positions will increase by 1, and when there is a '#', it decreases the leaf position by 1 as it seals 1 position. And at any moment, there should be at least 1 open leaf position for the new comer to attach to, until the end.
def isValidSerialization(self, preorder): preorder=preorder.split(',') leaves=1 for node in preorder: if leaves==0: return False leaves-=(1 if node=='#' else -1) return leaves==0