Verify Preorder Serialization of a Binary Tree(Medium)

One way to serialize a binary tree is to use pre-oder 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: "9,3,4,#,#,1,#,#,2,#,6,#,#" Return true

Example 2: "1,#" Return false

Example 3: "9,#,#,1" Return false

解题思路：基于Stack

可以在字符串里找"n##"这种结构（对应tree里两个children都是Null的叶节点），找到之后就把"n##"改写成"#"，也就是把找到的那个末端的子树想想成null，最后字符串变成"#"的就是valid，否则就invalid

比如

A) 9 3 "4 # #" "1 # #" 2 # "6 # #" ---> 9 3 # # 2 # # ---> 9 "3 # #" "2 # #" ---> 9 # # ---> "9 # #" ---> "#"

B) 9 3 "4 # #" "1 # #" ---> 9 3 # # ---> 9 "3 # #" ---> 9 # (没有"n##"结构了，return false)

public boolean isValidSerialization(String preorder) {
    if (preorder==null || preorder.length()==0) return false;
    String[] strs = preorder.split(",");
    Stack<String> st = new Stack<String>();

    for (int i=0; i<strs.length; i++) {
        String cur = strs[i];
        while (cur.equals("#") && st.size()>1 && st.peek().equals("#")) {
            st.pop();
            st.pop();
        }
        st.push(cur);
    }

    if (st.size()==1 && st.peek().equals("#")) return true;
    return false;
}

References

1 G面经Prepare: Valid Preorder traversal serialized String