331. Verify Preorder Serialization of a Binary Tree
1. Description
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 #.
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”.
2. Example
Example 1:
Input: “9,3,4,#,#,1,#,#,2,#,6,#,#”
Output: true
Example 2:
Input: “1,#”
Output: false
Example 3:
Input: “9,#,#,1”
Output: false
3. Solutions
My Accepted Solution
n = i_preorder.size()
Time complexity: O(n)
Space complexity: O(n)
// we could combine the part of spliting and judging, and we could just use a loop to pass the number, rather than seperate them
// but I think seperate them coud make the code clear and easy to understand
class Solution
{
private:
const int NULLPTR = 1;
const int NODE = 2;
public:
// bool isValidSerialization(string preorder)
bool isValidSerialization(const string &i_preorder)
{
// seperate nodes into a vector of string, since originally, the number is represented in char, it may have lots of digits, it is tedious to handle numbers
// now, all nodes are represented in string, they look like "123" or "#", we could handle them as same
vector<string> nodesVector;
istringstream inputStream(i_preorder);
for(string subString; getline(inputStream, subString, ','); nodesVector.push_back(subString));
// start judging the tree
// now, without ",", we only have two categories nodes: number and nullptr pointer
// nullptr pointer is a vaild tree(null tree)
// number is a invalid node(it must have valid left child and right child)
// if we face two nullptr pointers, that means two valid child tree, their parent tree is also valid
// so when we face two "#", and the node before them is a number, then the number node is valid as well. so we remove two "#", and turn the number into "#"(valid tree)
// otherwise, if the pattern is not "number # #", we put them back, and hope we could judge them in the future
// after this process, if the tree is valid, the stack will only have a valid tree "#"
stack<string> nodes; // store valid nodes and invalid nodes
for(int i = 0; i < nodesVector.size(); i++)
{
nodes.push(nodesVector[i]);
while(nodes.top() == "#" && nodes.size() >= 3)
{
nodes.pop();
auto node = nodes.top();
nodes.pop();
if(node == "#" && nodes.top() != "#")
{
nodes.top() = "#";
}
else
{
nodes.push(node);
nodes.push("#");
break;
}
}
}
return nodes.size() == 1 && nodes.top() == "#";
}
};
3.1 In-Degree and Out-Degree
n = i_preorder.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
private:
const int NULLPTR = 1;
const int NODE = 2;
public:
// bool isValidSerialization(string preorder)
bool isValidSerialization(const string &i_preorder)
{
vector<string> nodesVector;
istringstream inputStream(i_preorder);
for(string subString; getline(inputStream, subString, ','); nodesVector.push_back(subString));
// as a valid tree, the sum of all nodes' in-degree and out-degree should be equal(with leaf nodes)
// so we check the degree and judge whether the tree is valid
// every in-degree, we decrease 1, every out-degree, we increae 1
// the in-degree of root is 0, so to normalize the process, we let the difference be 1, to let root could decrease in-degree
int degreeDifferences = 1;
for(int i = 0; i < nodesVector.size(); i++)
{
if(nodesVector[i] != "#") degreeDifferences += 1;
else degreeDifferences -= 1;
if(degreeDifferences < 0) return false; // without out-degree, we can't continue construct child node, so the tree is invalid
if(degreeDifferences == 0 && i + 1 != nodesVector.size()) return false;
// the difference shoule be zero at the ending, but if it becomes zero during the process, the tree can't construct nodes continually
}
return degreeDifferences == 0;
}
};