Leetcode 331. Verify Preorder Serialization of a Binary Tree
The problem asks us to verify if a given preorder serialization of a binary tree is valid.
The given serialization is a string of comma-separated values where each value could either be an integer or a ‘#’ which denotes a null node.
According to the properties of preorder serialization, the root node appears first, followed by the left subtree, and then the right subtree. The task is to ensure that the given serialization represents a valid binary tree.
Assuming reasonable answers to these questions, we can proceed to the strategy.
To validate the serialization, we can use the concept of out-degree and in-degree. In a valid binary tree:
The main steps are:
slots
).slots
by 1 because every node takes a slot.slots
becomes negative any time before the end, it’s invalid.slots
by 2).slots
should be exactly 0.Here’s the Java code to implement the solution:
public class Solution {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int slots = 1; // Initially, we start with one slot for the root
for (String node : nodes) {
slots--; // One slot is taken by the current node
if (slots < 0) {
return false; // If slots become negative, it's invalid
}
if (!node.equals("#")) {
slots += 2; // Non-null nodes provide two new slots
}
}
return slots == 0;
}
}
The time complexity of this solution is O(n), where n is the length of the input string. This is because:
The space complexity is O(n) due to the storage of the split nodes array.
By using this approach, we efficiently determine the validity of the given preorder serialization of a binary tree.
Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?