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

Rust Solution

struct Solution;

impl Solution {
    fn is_valid_serialization(preorder: String) -> bool {
        let mut stack: Vec<char> = vec![];
        for tok in preorder.split(',') {
            if tok == "#" {
                while let Some('#') = stack.last() {
                    stack.pop();
                    if stack.pop().is_none() {
                        return false;
                    };
                }
                stack.push('#');
            } else {
                stack.push('$');
            }
        }
        stack == vec!['#']
    }
}

#[test]
fn test() {
    let preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#".to_string();
    let res = true;
    assert_eq!(Solution::is_valid_serialization(preorder), res);
    let preorder = "1,#".to_string();
    let res = false;
    assert_eq!(Solution::is_valid_serialization(preorder), res);
    let preorder = "9,#,#,1".to_string();
    let res = false;
    assert_eq!(Solution::is_valid_serialization(preorder), res);
    let preorder = "1,#,#,#,#".to_string();
    let res = false;
    assert_eq!(Solution::is_valid_serialization(preorder), res);
}

Having problems with this solution? Click here to submit an issue on github.