Java Easiest and Fast Solution With Explanation

  • 0

    First, let us think about the simplest binary tree:

     / \
    #   #

    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

      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) == '#') {
                } else {
            return counter == 0;

Log in to reply

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