Question

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

Thinking:

  • Method:
    • 最后一个字符一定是一个#。
    • 我们发现，数字的个数一定比#少一个。
    • 如果我们发现了除了最后一个#，我们发现到当前的字符，#的个数大于数字的个数，就可以返回false。
class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] tokens = preorder.split(",");
        int len = tokens.length;
        int count = 0;
        for(int i = 0; i < len - 1; i++){
            if(!tokens[i].equals("#")){
                count ++;
            }else{
                count --;
            }
            if(count < 0) return false;
        }
        return count == 0 && tokens[len - 1].equals("#");
    }
}

Reference

  1. [LeetCode] Verify Preorder Serialization of a Binary Tree 验证二叉树的先序序列化