LeetCode 331: Verify Preorder Serialization of a Binary Tree

Explanation

To verify if a given preorder serialization of a binary tree is valid, we can simulate the process of building the tree using a stack. We iterate over the nodes in the preorder serialization and push them onto the stack. Whenever we encounter two consecutive "#" nodes on top of the stack, we pop them along with the parent node and replace them with a single "#". We repeat this process until the stack contains only one element, which should be "#" (representing the root node).

Algorithm:

1. Split the input preorder string by commas to get individual nodes.
2. Initialize an empty stack.
3. Iterate over each node in the preorder list.
   • Push the current node onto the stack.
   • Check if the top two elements on the stack are "#" and pop them along with the parent node until we cannot perform this operation.
4. After iterating through all nodes, check if the stack contains only one element "#" which represents a valid binary tree serialization.

Time Complexity: O(n) where n is the number of nodes in the preorder serialization string. Space Complexity: O(n) where n is the number of nodes in the preorder serialization string.

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        
        for (String node : nodes) {
            stack.push(node);
            
            while (stack.size() >= 3 && stack.get(stack.size() - 1).equals("#") && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        
        return stack.size() == 1 && stack.peek().equals("#");
    }
}