Java, Stack implementation, check preorder traversal, check BST validation
the preorder sequence is the dfs sequence. \n In dfs, each non-null node, visited exactly 3 times (null node just 1 time). 1 from inserting into stack, the othe
* the preorder sequence is the dfs sequence. \n* In dfs, each non-null node, visited exactly 3 times (null node just 1 time). 1 from inserting into stack, the other 2 from backtracking from two children. \n* Thus, if we can keep tracking the visiting count for each node, we will have:\n\t* if count[index] == 1 // just visit this node and insert into stack\n\t* if count[index] == 2 // backtracking from left child (we can also **check left < root for BST validation**)\n\t* if count[index] == 3 // backtracking from right child (we can also **check right > root for BST validation**)\n\n```\n    public boolean isValidSerialization(String preorder) {\n        String[] nodes = preorder.split(",");\n        int n = nodes.length;\n        int[] count = new int[n]; // record visited times\n        Stack<Integer> stack = new Stack<Integer>(); // keep curt dfs visiting nodes\' index\n        \n        int i = 0;\n        if(!nodes[i].equals("#")) stack.push(i); // check if the tree is only "#"\n        count[i]++;\n        \n        while(!stack.isEmpty() && i != n - 1 && count[stack.peek()] < 3) {\n            i++;\n            stack.push(i);\n            count[i]++;\n            while(!stack.isEmpty() && (nodes[stack.peek()].equals("#") || count[stack.peek()] == 3)) { \n                int childIndex = stack.pop();\n                if(!stack.isEmpty()) {\n                \tcount[stack.peek()]++; // backtracking to parent, count +1\n                \tif(count[stack.peek()] == 2 && !nodes[childIndex].equals("#")) {\n                \t\tif(Integer.parseInt(nodes[childIndex]) > Integer.parseInt(nodes[stack.peek()])) {\n                \t\t\treturn false;\n                \t\t}\n                \t}\n                \tif(count[stack.peek()] == 3 && !nodes[childIndex].equals("#")) {\n                \t\tif(Integer.parseInt(nodes[childIndex]) < Integer.parseInt(nodes[stack.peek()])) {\n                \t\t\treturn false;\n                \t\t}\n                \t}\n                }\n            }\n        }\n        \n        if(i == n - 1 && stack.isEmpty()) return true;\n        else return false;\n    }\n```
[]