traditional Java traversal solution

  • 0

    not as smart as the in-out degree solution, but easy to come up from tree traversal algorithm.

        public boolean isValidSerialization(String preorder) {
            if (preorder.length() == 0) return true;
            String[] tokens = preorder.split(",");
            return next(tokens, 0) == tokens.length;
        public int next(String[] preorder, int start) {
            if (start >= preorder.length) return -1;
            String root = preorder[start++];
            if (root.equals("#")) return start;
            if (start >= preorder.length) return -1;
            int leftEnd = next(preorder, start);
            if (leftEnd == -1) return -1;
            return next(preorder, leftEnd);

Log in to reply

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