Question
Formatted question description: https://leetcode.ca/all/331.html
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
@tag-tree
Algorithm
- The number of digits is always one less than
#
- The last one must be
#
- leaf node:
number, #, #
If we initialize a counter to 0,
- When a number is encountered, the counter increases by 1,
- When the # sign is encountered, the counter is decreased by 1, Then the counter should still be 0 at the end.
Two examples that return False, #,7,6,9,#,#,#
and 7,2,#,2,#,#,#,6,#
, then through these two counter examples,
- If the root node is empty, there can be no more nodes behind,
- And there cannot be three consecutive
#
signs.
So when we add or subtract the counter, if we encounter the #
number, and the counter is already 0, and then subtracted to become a negative number, we directly return False, because in the correct sequence, any position i is in [ 0, i]
The number of # numbers in the range is not greater than the number of digits.
When the loop is complete, we check whether the counter is 0 and also see whether the last character is #
sign.
Code
Java
import java.util.Stack;
public class Verify_Preorder_Serialization_of_a_Binary_Tree {
// https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution
public class Solution_noStack {
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1; // if single node tree [root]
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}
}
public class Solution {
public boolean isValidSerialization(String preorder) {
if (preorder == null || preorder.length() == 0) {
return true;
}
String[] nodes = preorder.split(",");
Stack<String> stack = new Stack<>();
for (String node : nodes) {
if (node.equals("#")) {
// after first while loop, current node can be deemed as #
while (!stack.isEmpty() && stack.peek().equals("#")) {
stack.pop(); // pop # in stack
if (stack.isEmpty()) { // should leave a number in stack
return false;
}
stack.pop(); // pop val with left-# and right-# => repalce it with #
}
}
stack.push(node);
}
return stack.size() == 1 && stack.peek().equals("#");
}
}
}