You only need to count open leaf positions, short python 48ms, 88.5%


  • 3
    C

    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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.