Java Easiest and Fast Solution With Explanation


  • 0
    L

    First, let us think about the simplest binary tree:

      1
     / \
    #   #
    

    we can find out that with root node, initially, we should have 2 null node as the child of root node.

    now we add one node

       1
       /\
      2  #
     /\
    #  #
    

    we can find out that when we add a node, we need one more null node. so we use a counter to record how many null node we should expect in the future while we iterate the preorder string. and we know that in the end, the counter should be 0 since all the not-null leaf node should have null child node.

    we also know that when the counter is 0, we should expect no node in the future, beacause all the not-null leaves node are fulfiled, any other node should belong to another tree.

    Here is my code

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            int counter = 1;
            String[] splited = preorder.split(",");
            for (String s : splited) {
                // when counter is 0 and we are not at the end of the preorder string, the origin tree have been fulfiled, the rest node should belong to other tree
                if (counter <= 0) {
                    return false;
                }
                if (s.charAt(0) == '#') {
                    counter--;
                } else {
                    counter++;
                }
            }
            return counter == 0;
        }
    }
    

Log in to reply
 

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