JAVA, Counting Indegree and Outdegree, SIMPLE & CLEAR!


  • 52
    J
     public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        int degree = -1;         // root has no indegree, for compensate init with -1
        for (String str: strs) {
            degree++;             // all nodes have 1 indegree (root compensated)
            if (degree > 0) {     // total degree should never exceeds 0
                return false;
            }      
            if (!str.equals("#")) {// only non-leaf node has 2 outdegree
                degree -= 2;
            }  
        }
        return degree == 0;
    }

  • 0
    C

    clear logic! awesome!


  • 0
    M

    You got the essence of this question.


  • 0

    Bravo!!!!!!!!!!!!


  • 0
    C

    brilliant!!!!!!!!!!!!!!


  • 0
    J

    Why total degree should never exceed 0 ? Can you explain a little bit more ? Thank you !


  • 0
    M

    @JosephTao Since this is a preorder serialization, degrees are calculated in a top-down fashion, and, tree is a structure that each node has only one indegree and at most two outdegree. Positive degree means there are more indegree than outdegree, which violates the definition.


  • 0
    W

    If Input is [2 # 1 # #], it is invalid, but this solution would return true, right?

              2
          /      \
        #        #
     /    \
    1    #
    

    Here is what happens at each stage. degree starts at -1
    loop 1: str="2" --> degree = (-1+1)-2 = -2
    loop 2: str="#" --> degree = (-2+1) = -1
    loop 3: str="1" --> degree = (-1+1)-2 = -2
    loop 4: str="#" --> degree = (-2+1) = -1
    loop 5: str="#" --> degree = (-1+1) = 0
    return true


  • 1
    G

    @webmihir "2,#,1,#,#" is

        2
    #      1
         #   #
    

Log in to reply
 

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