An easy recursive Java Solution that beats 99.9%


  • 0
    I

    Traverse the tree by moving iter over the preorder string.
    (1) Use a traverse function to move iter, return -1 if invalid.
    (2) If s[iter] is '#', it is a leaf node, and we only need to skip it and a comma. So return iter+2.
    (3) Else, the node must have a left child and right child, move iter to the start of the left tree by finding the first comma which separate the node and the left tree. If there is no comma, it means there is no left, which is invalid, return -1. Else just traverse the left and right subtree.
    (4) After traverse, since we assume all node follow a comma, so iter == preorder.length() +1 means the string is the valid compression of the tree.

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            if(preorder == null || preorder.length() == 0) return false;
            return traverse(preorder, 0) == preorder.length() + 1;
        }
        
        private int traverse(String s, int iter){
            if(iter < 0 || iter >= s.length()) return -1; //invalid
            if(s.charAt(iter) == '#'){
                //leaf node, skip # and a comma
                return iter + 2;
            }
            else{
                //a node with two subtree
                iter = s.indexOf(',', iter); //skip the value of the node
                if(iter == -1) return -1; //a value with out comma means it has no child append, which is wrong
                iter++; //skip the comma
                iter = traverse(s, iter); //traverse the left subtree
                iter = traverse(s, iter); //traverse the right subtree
                return iter;
             }
        }
    }
    

Log in to reply
 

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