12ms Java Solution with a stack


  • 0
    F
    public boolean isValidSerialization(String preorder) {
            if(preorder.length() == 0){
                return false;
            }
            
            int cnt;
            Stack<Integer> stack = new Stack<>();
            
            for(cnt = 0; cnt < preorder.length(); cnt++){
                if(preorder.charAt(cnt) == '#'){
                    ++cnt;
                    while(!stack.empty() && stack.peek()==1){
                        stack.pop();
                    }
                    if(stack.empty()){  //A tree has already be constructed.
                        break;
                    } else {
                        stack.pop();
                        stack.push(1);
                    }
                } else {
                    stack.push(0);
                    while(cnt<preorder.length() && preorder.charAt(cnt)>='0' && preorder.charAt(cnt)<='9'){
                        ++cnt;
                    }
                }
            }
            
            return cnt==preorder.length() && stack.empty();
        }

Log in to reply
 

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