Java intuitive 22ms solution with stack
See detailed comments below. Time complexity is O(n), space is also O(n) for the stack.\n\n    public class Solution {\n        public boolean isValidSerializat
See detailed comments below. Time complexity is O(n), space is also O(n) for the stack.\n\n    public class Solution {\n        public boolean isValidSerialization(String preorder) {\n            // using a stack, scan left to right\n            // case 1: we see a number, just push it to the stack\n            // case 2: we see #, check if the top of stack is also #\n            // if so, pop #, pop the number in a while loop, until top of stack is not #\n            // if not, push it to stack\n            // in the end, check if stack size is 1, and stack top is #\n            if (preorder == null) {\n                return false;\n            }\n            Stack<String> st = new Stack<>();\n            String[] strs = preorder.split(",");\n            for (int pos = 0; pos < strs.length; pos++) {\n                String curr = strs[pos];\n                while (curr.equals("#") && !st.isEmpty() && st.peek().equals(curr)) {\n                    st.pop();\n                    if (st.isEmpty()) {\n                        return false;\n                    }\n                    st.pop();\n                }\n                st.push(curr);\n            }\n            return st.size() == 1 && st.peek().equals("#");\n        }\n    }
['Stack', 'Java']