# 331. Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use pre-order 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 #.
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
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".
Example 1:
Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
Example 2:
Input: "1,#"
Output: false
Example 3:
Input: "9,#,#,1"
Output: false
# Solution
Approach 1: observe that in a preorder traversal, two consecutive #s means the previous number is a leaf. Use a stack to 'reduce' all leafs and we should be able to clear out the stack.
Approach 2: an extension to the stack based approach -- the numbers doesn't matter, just count the number of available leaf slots.
Approach 3: (this approach goes TLE) a valid preorder serialization can be broken up to 3 parts: the first item being a number, and two subtrees that are both valid preorder serializations (recursion). Can use a cache or dp to speed things up.
# Code (Python)
Approach 1:
def isValidSerialization(self, preorder):
stack = []
for node in preorder.split(','):
stack.append(node)
# to 'reduce' leaves: when seeing two consecutive #s on stack, pop both and replace the topmost element on the stack with a single #, essentially replacing a leaf with a null value
while len(stack) >= 3 and stack[-2:] == ['#', '#']:
if stack[-3] == '#': # a leaf can't have children
return False
stack[-3:] = '#'
return stack == ['#']
Approach 2:
def isValidSerialization(self, preorder):
available_slots = 1
for node in preorder.split(','):
if available_slots <= 0:
return False
if node != '#':
available_slots += 1 # the number takes a slot, but increase 2 slots
else:
available_slots -= 1 # the pound takes a slot
return available_slots == 0
Approach 3:
def isValidSerialization(self, preorder):
sequence = preorder.split(',')
cache = {}
return self._is_valid_preorder(sequence, 0, len(sequence) - 1, cache)
def _is_valid_preorder(self, sequence, start, end, cache):
# a leaf node can only be a #, not number
if start == end:
return sequence[start] == '#'
# a root can't be a #
if sequence[start] == '#':
return False
for i in range(start + 1, end):
if (start + 1, i) not in cache:
cache[(start + 1, i)] = self._is_valid_preorder(sequence, start + 1, i, cache)
first_half_valid = cache[(start + 1, i)]
if (i + 1, end) not in cache:
cache[(i + 1, end)] = self._is_valid_preorder(sequence, i + 1, end, cache)
second_half_valid = cache[(i + 1, end)]
if first_half_valid and second_half_valid:
return True
return False
# Code (C++)
Approach 1:
// Stack - O(n) space.
class Solution {
public:
bool isValidSerialization(string preorder) {
stack<string> st;
int head = 0;
int tail = 1;
while (tail <= preorder.size())
{
if (tail == preorder.size() || preorder[tail] == ',')
{
string node = preorder.substr(head, tail - head);
head = tail + 1;
if (node == "#")
{
while (!st.empty() && st.top() == "#")
{
st.pop();
if (st.empty())
return false;
st.pop();
}
}
st.push(node);
}
tail++;
}
return (st.size() == 1 && st.top() == "#");
}
};
Approach 2:
// O(1) space.
class Solution {
public:
bool isValidSerialization(string preorder) {
int head = 0;
int tail = 1;
int open = 1;
while (tail <= preorder.size())
{
if (tail == preorder.size() || preorder[tail] == ',')
{
string node = preorder.substr(head, tail - head);
head = tail + 1;
if (node == "#")
open--;
else
open++;
if (open == 0 && tail < preorder.size())
return false;
}
tail++;
}
return open == 0;
}
};
Approach 3:
// Time Limit Exceeded.
class Solution {
public:
bool isValidSerialization(string preorder) {
// Retrive all nodes from the string.
vector<string> nodes;
int head = 0;
int tail = 1;
while (tail <= preorder.size())
{
if (tail == preorder.size() || preorder[tail] == ',')
{
string node = preorder.substr(head, tail - head);
head = tail + 1;
nodes.push_back(node);
}
tail++;
}
int n = nodes.size();
bool status[n][n];
for (int i = 0; i < n; ++i)
{
status[i][i] = nodes[i] == "#";
}
for (int len = 2; len <= n; ++len)
{
for (int tail = n-1; tail - len + 1 >= 0; --tail)
{
int head = tail - len + 1;
status[head][tail] = false;
if (nodes[head] == "#")
continue;
for (int i = head + 1; i < tail; ++i)
{
if (status[head+1][i] && status[i+1][tail])
{
status[head][tail] = true;
break;
}
}
}
}
return status[0][n-1];
}
};