331. Verify Preorder Serialization of a Binary Tree

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        """ tc O(N) sc O(N)
        1. remove `,` and save it into arr
        2. loop through arr and check current node if is None 
        3. if yes, diff + 2 else diff -1
                 9
              -1/ \-1
               3   2
          -1  /\-1  \ -1
             4  1    6
   every indegree +1; outdegree -1   except root node,  there are two state of node: (1)empty:  1 indegree 0 out degree (2)non-empty: 1 indegree 2 outdegree
   => need to make sure each step maintain total state sum balanced   
       """
        nodes = preorder.split(',')
        diff = 1 
        for node in nodes:
            # note the order can't change otherwise we need to change the return condition since there are edge cases there are 1 node 
            diff -= 1  
            if diff < 0 :
                return False
            if node != '#':
                diff += 2

        return diff == 0

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        """ tc O(N) sc O(N)
when you iterate through the preorder traversal string, for each char:

case 1: you see a number c, means you begin to expand a new tree rooted with c, you push it to stack

case 2.1: you see a #, while top of stack is a number, you know this # is a left null child, put it there as a mark for next coming node k to know it is being the right child.

case 2.2: you see a #, while top of stack is #, you know you meet this # as right null child, you now cancel the sub tree (rooted as t, for example) with these two-# children. But wait, after the cancellation, you continue to check top of stack is whether # or a number:

---- if a number, say u, you know you just cancelled a node t which is left child of u. You need to leave a # mark to the top of stack. So that the next node know it is a right child.

---- if a #, you know you just cancelled a tree whose root, t, is the right child of u. So you continue to cancel sub tree of u, and the process goes on and on.
       """
        nodes = preorder.split(',')
        st = [] 
        for node in nodes:
            while node =='#' and st and st[-1] == node:  #  current node is leaf node 
                st.pop()
                if not st: # stack is empty
                    return False
                st.pop() # here st pops a parent node 
            st.append(node) #if it is leaf node, push one back to compensate with cases where parent node has only one child 
        return len(st) == 1 and st[-1] == '#'