C++ - Easy to Understand, Divide and Conquer, Recursive

  • 0

    This idea come from some posts in Serialize and Deserialize a Binary Tree.

    Intrinsically, it is equivalent with other methods using stack.

    The key idea is to check two required conditions:
    The preorder string is

    1. not too short (long enough to build a tree)
    2. not too long (the whole string is used)
    class Solution {
        bool isValidSerialization(string preorder) {
            stringstream ss(preorder);
            // two conditions are required:
            // 1. not too short
            // 2. not too long
            return notTooShort(ss) && ss.eof() == true;
        bool notTooShort(stringstream &ss) {
            string val_str;
            getline(ss, val_str, ',');
            // too short
            if (val_str.empty()) {
                return false;
            if (val_str == "#") {
                return true;
            // not too short for both left and right child
            return notTooShort(ss) && notTooShort(ss);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.