Straight-forward C++ solution with explanation


  • 19
    C

    The idea is simple.

    Denote the number of null nodes as nullCnt, the number of actual nodes as nodeCnt.

    For a binary tree, the number of null nodes is always the number of actual nodes plus 1. nullCnt==nodeCnt+1;

    So,

    1. if nullCnt>nodeCnt+1, the tree is invalid.
    2. if nullCnt<nodeCnt+1, the tree is incomplete.
    3. if nullCnt==nodeCnt+1, the tree is complete and can't be extended.

    We just need to keep track of nullCnt and nodeCnt as we go through the sequence and check these conditions above.

    Actually, recording nullCnt-nodeCnt is enough, so you can further improve the code.

    class Solution {
    public:
        bool isValidSerialization(string preorder) {
            int nodeCnt=0,nullCnt=0;
            vector<string> v=splitStr(preorder,',');
            for(int i = 0; i<v.size(); i++){
                if(v[i]=="#") ++nullCnt;
                else ++nodeCnt;
                if(nullCnt>=nodeCnt+1 && i!=v.size()-1) return false;
            }
            return nullCnt==nodeCnt+1;
        }
        
        vector<string> splitStr(string str, char delimiter){
        	vector<string> r;
        	string tmpstr;
        	while (!str.empty()){
        		int ind = str.find_first_of(delimiter);
        		if (ind == -1){
        			r.push_back(str);
        			str.clear();
        		}
        		else{
        			r.push_back(str.substr(0, ind));
        			str = str.substr(ind + 1, str.size() - ind - 1);
        		}
        	}
        	return r;
        }
    };
    

    Edit:
    The algorithm scans the string one node at a time from the beginning, once it finds nullCnt>nodeCnt+1, it stops and return false.

    If it finds nullCnt==nodeCnt+1, that means by now, the tree is valid(otherwise the algorithm would return false before this) and complete, if there are more nodes to come, it returns false; if it's the last node, the algorithm returns true.

    If it finds nullCnt<nodeCnt+1, that means the tree is incomplete but not invalid(or the algorithm would return false before this) by now, if this is the last node and no more nodes comes after it, the tree is invalid.

    Example:

    "#,1,#" 1st node is #, nullCnt==1, nodeCnt==0, nullCnt==nodeCnt+1, the tree is complete by now, but there are more nodes after it, so it's invalid.

    "1, #" 1st node is 1, nullCnt==0, nodeCnt==1, nullCnt<nodeCnt+1, the tree is incomplete, but there are more nodes after it, so we proceed, 2nd node is #, nullCnt==1, nodeCnt==1, nullCnt<nodeCnt+1, the tree is incomplete and there are no more nodes left, so it's invalid.

    Edit2:

    Why for a binary tree, nullCnt==nodeCnt+1?

    For an empty binary tree, nullCnt=1, nodeCnt=0, nullCnt==nodeCnt+1.

    Each time we add an actual node, we take the place of one null node and create two null nodes, so the net gain of null node is one, which is also the net gain of actual node. Thus, the actual nodes and null nodes will increase by the same amount, which means nullCnt==nodeCnt+1 will always hold.


  • 0

    nice idea!

    I am wondering whether there are simpler API to split the string to vector of string in C++ as this is a common operation.

    Can we directly to split the string to vector<string> without implement is by your self ??

    Except the "strtok" in C, It is like this

    /* strtok example */
    #include <stdio.h>
    #include <string.h>
    
    int main ()
    {
      char str[] ="- This, a sample string.";
      char * pch;
      printf ("Splitting string \"%s\" into tokens:\n",str);
      pch = strtok (str," ,.-");
      while (pch != NULL)
      {
        printf ("%s\n",pch);
        pch = strtok (NULL, " ,.-");
      }
      return 0;
    }

  • 0

    Only count the number of the null-node and the non-null node can ensure the tree is OK ????? Is this condition Complete ???


  • 0

    I think the count relationship is only the necessary condition but not the complete conditions !


  • 0
    Z

    I don't think just counting is enough.

    An easy counter case could be "#,1,#". This is clearly an invalid case, but it would pass with your code.


  • 0
    C

    My original post might be a little misleading, so I edited the post to clarify it for you.


  • 4
    Z

    Thanks for the clarification. I think your algorithm should work.
    Using stringstream can make parsing a bit easier:

    stringstream ss.str(preorder);
    string t;
    vector<string> v;
    while (getline(ss, t, ',') {
    v.push_back(t);
    }

  • 0
    I

    Why is it true that null nodes is number of actual nodes + 1?


  • 1
    B

    I think my idea is similar to yours. But since the question says:

    You may assume that the input format is always valid, for example it
    could never contain two consecutive commas such as "1,,3".

    We could just scan the string once and have no worry about the format.

    bool isValidSerialization(char* preorder) {
        int nulls, nodes;
        char pre;
        
        for (nulls = nodes = 0; *preorder; pre = *preorder++)
            if (*preorder == ',') {
                pre == '#' ? nulls++ : nodes++;
                if (nodes < nulls)
                    return false;
            }
        return pre == '#' && nulls == nodes;
    }

  • 0
    C

    You can prove that by induction. I added it to the bottom of the post.


Log in to reply
 

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