Guest User

Grokking 226

a guest
Jul 13th, 2022
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.90 KB | None | 0 0
  1. class Solution {
  2.     public boolean isValidSerialization(String preorder) {
  3.         // Initially, there is one empty slot
  4.         int emptyLeaf = 1;
  5.        
  6.         for (int i = 0; i < preorder.length(); i++) {
  7.             if (emptyLeaf == 0) return false;
  8.            
  9.             char c = preorder.charAt(i);
  10.             if (c == ',') {
  11.                 continue;
  12.             }
  13.  
  14.             // If the next token is not ',' or '#' then it's a node, add 2 slots for 2 children of that node
  15.             if (c != '#') {
  16.                 emptyLeaf += 2;
  17.                 int j = i;
  18.                 while (j < preorder.length() && preorder.charAt(j) != ',') j++;
  19.                 i = j - 1;
  20.             }
  21.  
  22.             // Whether the token is '#' or a node, it takes 1 empty slot
  23.             emptyLeaf -= 1;
  24.             if (emptyLeaf < 0) return false;
  25.         }
  26.         return emptyLeaf == 0;
  27.     }
  28. }
Add Comment
Please, Sign In to add comment