Simple 8ms C++ solution with only one int variable


  • 0
    P

    For any binary tree, the difference between the number of null nodes and the full nodes should be exactly one. This applies for the subtrees as well. All we need to do is maintain one variable which increments when encountering a node and decrements when we see a null node. The following rules must hold for count = #Nodes with values - #NULL nodes

    1. At any point of time, the count cannot be below -1 while iterating.

    2. After processing all nodes, the count must be exactly -1.

      class Solution {
      public:
      bool isValidSerialization(string preorder) {
      int count = 0;
      int start = 0;
      int found = preorder.find(",");
      while (found >= 0) {
      if (count == -1) return false;
      string val = preorder.substr(start, found - start);
      if (val[0] == '#') {
      count--;
      }
      else count++;
      start = found + 1;
      found = preorder.find(",",found + 1);
      }
      string val = preorder.substr(start);
      if (val[0] == '#') count--;
      else count++;
      if (count != -1) return false;
      else return true;
      }
      };


Log in to reply
 

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