Share my C++ solution with demonstration figure,easy to understand


  • 0
    V
    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            int n = preorder.size();
            int i = 0, j = 0;
            string tmp, tmp2;
            stack<string> s;
            
            if (n == 0)
                return false;
            if (preorder[0] == '#')
            {
                if (n == 1)
                    return true;
                return false;
            }
    
            while (preorder[i] == ' ')
                ++i;
    
            while (i < n)
            {
                if (isdigit(preorder[i]))
                {
                    j = i;
                    while (i+1 < n && isdigit(preorder[i+1]))
                        ++i;
                    string num = preorder.substr(j, i-j+1);//get the integer
                    s.push(num);
                }
                else if (preorder[i] == '#')
                {
                    tmp = s.top();
                    //in this case:integer,#,#.We could consider it as a subtree which can be eliminated and replaced by a #.
                    while (tmp[0] == '#' && s.size() > 1)
                    {
                        s.pop();
                        tmp2 = s.top();
                        if (tmp2[0] == '#')
                            return false;
                        
                        s.pop();
                        
                        if (s.size() != 0)
                            tmp = s.top();
                    }
                    s.push("#");
                }
                ++i;
            }
            
            if (s.size() == 1 && s.top() == "#")
                return true;
            
            return false;
        }
    };

  • 0
    V
         _9_
        /   \
       3     2
      / \   / \
     4   1  #  6
    / \ / \   / \
    # # # #   # #
    
           ||
           ||
           \/
    
         _9_
        /   \
       3     2
      / \   / \
     #   1  #  6
        / \   / \
        # #   # #
    
           ||
           ||
           \/
    
         _9_
        /   \
       3     2
      / \   / \
     #   #  #  6
              / \
              # #
    
           ||
           ||
           \/
    
         _9_
        /   \
       #     2
            / \
            #  6
              / \
              # #
    
           ||
           ||
           \/
    
         _9_
        /   \
       #     2
            / \
            #  #
    
    
           ||
           ||
           \/
    
         _9_
        /   \
       #     #
    
    
           ||
           ||
           \/
    
         _#_
    

Log in to reply
 

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