Verify Preorder Serialization of a Binary Tree - Medium - L
Published:
Question
- https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
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 ‘#’. 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.
Approach
- Create a stack
- If # is encountered then reduce the count of top element by 1
- If count of top element reaches 0 then pop that element
- If an element is poped the reducte the count of top element by 1
- If # is not encountered then push the element
- In the end check if stack is empty
- If stack is empty at start of the loop then return false. (also if it is non zeroth element)
Solution
class Solution {
public static class NumCount {
private String x;
private int c;
public NumCount(String x) {
this.x = x;
c = 2;
}
public String val() {
return x;
}
public int dec() {
c--;
return c;
}
public String toString() {
return x;
}
}
public boolean isValidSerialization(String preorder) {
String[] words = preorder.split(",");
Stack<NumCount> stack = new Stack<>();
int n = words.length;
for (int i = 0; i < n; i++) {
if (i != 0 && stack.isEmpty()) return false;
if ("#".equals(words[i]))
while (!stack.isEmpty() && stack.peek().dec() == 0)
stack.pop();
else
stack.push(new NumCount(words[i]));
}
return (stack.size() == 0);
}
}