Preorder Serialization Verification of a Binary Tree (Deprecated)
Given a particular kind of preorder serialization of a binary tree, verify that it's valid. Tags: Recursion, Trees
Try It!
Discussion
Video
Solution
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
# remember how many empty slots we have
# non-null nodes occupy one slot but create two new slots
# null nodes occupy one slot
preorder = preorder.split(',')
#initially we have one empty slot to put the root in it
count = 1
for node in preorder:
# no empty slot to put the current node
if count == 0:
return False
# a null node?
if node == '#':
# ocuppy slot
count -= 1
else:
# use a slot, create 2 new slots
count += 1
#we don't allow empty slots at the end
return count == 0