Problem Description
One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.
Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.
It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid.
- For example, it could never contain two consecutive commas, such as
"1,,3".
Note: You are not allowed to reconstruct the tree.
Example 1:
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true
Example 2:
Input: preorder = "1,#" Output: false
Example 3:
Input: preorder = "9,#,#,1" Output: false
Constraints:
1 <= preorder.length <= 10^4preorderconsist of integers in the range[0, 100]and'#'separated by commas','.
The description was taken from https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/.
Problem Solution
#O(N) Time, O(1) Space
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
children = 1 for i, node in enumerate(preorder):
#For handling nodes with multiple digit values
if i < len(preorder) -1 and preorder[i+1].isdigit():
continue
if node != ",":
children -= 1
if children < 0:
return False
if node.isdigit():
children += 2
return not childrenProblem Explanation
The problem description is a bit confusing, but what we're wanting to do is verify that each child node is accounted for in the preorder traversal, including the null ones and that there are no more child nodes than possible.
The idea behind this is that each non-null node object has two attribute pointers, a left, and a right child node.
That means that if we visit a non-null node, then we would expect it to have two child node pointers based on the node class attributes and we can expect to account for two more nodes later in the traversal.
To solve this problem, we can traverse the preorder traversal with a running counter of children we expect to see.
Each time we come across a node, we will decrement that counter by one. If that node is non-null, we will increment the number by two.
Once we finish traversing the tree, that counter should be zero to signify we accounted for all of the child nodes, no more and no less.
Let's start by initializing our children counter to one since we just have our root node at this point.
children = 1
Next, we will enumerate through the preorder traversal.
An enumeration is a traversal through the values of the string while keeping a counter so that we can track indices as well.
for i, node in enumerate(preorder):
First off, if we aren't at the last character of the string and the character directly after the current one is also a digit then we will continue to the next iteration.
We are looking at a comma-delimited string that separates the traversed nodes so if we have two digits next to each other then that means they belong to the same node that has a multiple digit value.
This lets us avoid decrementing the children counter multiple times for the same node and allows us to only decrement it once we get to the last digit of the node's value.
if i < len(preorder) -1 and preorder[i+1].isdigit():
continue
Otherwise, if the current character isn't a comma, then it is a number or a pound sign, both signify a node.
If we come across a node, we will decrement the children counter by one.
if node != ",":
children -= 1
If the children counter is less than zero, then we accounted for more children than were possible so we will return false.
if children < 0:
return False
If the current node is a digit, then it is not null so we can account for exactly two more nodes we expect to come across later.
if node.isdigit():
children += 2
Once we have traversed the string, we shouldn't have any more children to account for.
We will return whether or not this is the case.
return not children