Two ways in Java


  • 0
    L

    The first method uses indegree and outdegree to verify if the string gets exhausted.

    The second method will perform a regular preorder traversal till it is exhausted.

    public class Solution {
    
     int count;
     
     public boolean isValidSerialization(String pre) {
        String[] preorder = pre.split(",");
        return traverse(preorder) && count==preorder.length;
     }
     
     public boolean traverse(String[] s) {
        if(count>=s.length) {
            return false;
        }
        else if(s[count++].equals("#")) {
            //leaf node.
            return true;
        }
        //left and the right children.
        return traverse(s) && traverse(s);
     }
     
     
    
     public boolean isValidSerialization_it(String pre)
      {
        String[] preorder = pre.split(",");
        // "9,3,4,#,#,1,#,#,2,#,6,#,#"
        // add count when a root node is found and
        // remove counts when a null node is found.
        int count = 1;
        for (String s : preorder)
        {
          // remove the reference to the root node that we just added.
          if (--count < 0)
          {
            return false;
          }      
            
          if (!s.equals("#"))
          {
            // a root node is found.
            // add 2 children node for this because each root will have two
            // children.
            count += 2;
          }
        }
        return count == 0;
      }
     
    
    
    }
    

Log in to reply
 

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