Another stack solution with explanation


  • 0
    L

    If we follow two rules to fill the stack:

    1. if previous is non-null node, we push 'L'
    2. if previous is null node we regard current as 'R', so we pop stack

    For example:
    "9,3,4,#, #,1,#,#,2,#,6,#,#"
    M L L L R R L R R L R L R

    M here doesn't count, it's just for convenience.

    public boolean isValidSerialization(String preorder) {
        if (preorder == null) return false;
        
        String[] nodes = preorder.split(",");
        if (nodes.length == 1 && !nodes[0].equals("#"))
            return false;
        
        Stack<Character> st = new Stack<>();
        
        for (int i = 1; i < nodes.length; i++) {
            if (!nodes[i - 1].equals("#")) {
                st.push('L');
            } else {
                st.empty() ? return false : st.pop();
            }
        }
        
        return st.empty();
    }

Log in to reply
 

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