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


  • 0
    X

    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 {
    public:
        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;
        }
    private:
        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.