My clean Java code using a logical stack, O(n) time + O(1) space


  • 0
    H
    private int stack;
        
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        int i = findLeft(nodes, 0);        
        while (stack > 0) {
            stack--;
            i = findLeft(nodes, ++i);
        }        
        return i == nodes.length - 1;
    }
        
    private int findLeft(String[] nodes, int i) {
        while (i < nodes.length && !nodes[i].equals("#")) {
            stack++;
            i++;
        }        
        return i;
    }
    

Log in to reply
 

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