Leetcode skimming -- verifying the preorder serialization of binary tree ＃ 331 ＃ medium

Discussion and source code of the idea of verifying the preorder serialization of binary tree
     The topic of verifying the preorder serialization of binary tree is shown in the following figure , This problem belongs to stack and binary tree type , It mainly focuses on the use of search methods and the understanding of tree structure . The title of this article, the author thought 2 Methods , They are stack method and input / output method , The stack method uses Java Compiling , The in and out method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .

     I think this problem can be solved by stack method , First calculate the length of the string , And initialize a double ended queue , And press an element 1. Start traversing the loop , When the double ended queue is empty, the result of no is returned directly , When the character value is comma, skip directly , When the character value is ’#' The header element of the double ended queue is taken out and subtracted 1, Then judge whether it is greater than 0, If yes, put back the head of the double ended queue ; Otherwise, subtract the element at the top of the stack 1 Then press another 2, To traverse the loop , Until the end of the last traversal, judge whether the double ended queue is empty and return the judgment result . Then according to this idea, our Java The code is as follows ：

# Fire breathing dragon and water arrow turtle 
class Solution {
    public boolean isValidSerialization(String preorder) {
        int preorderLen = preorder.length();
        int ir = 0;
        Deque<Integer> stackList = new LinkedList<Integer>();
        stackList.push(1);
        while (ir < preorderLen) {
            if (stackList.isEmpty()) {
                return false;
            }
            if (preorder.charAt(ir) == ',') {
                ir = ir + 1;
            } else if (preorder.charAt(ir) == '#'){
                int topNum = stackList.pop() - 1;
                if (topNum > 0) {
                    stackList.push(topNum);
                }
                ir = ir + 1;
            } else {
                while (ir < preorderLen && preorder.charAt(ir) != ',') {
                    ir = ir + 1;
                }
                int topNum = stackList.pop() - 1;
                if (topNum > 0) {
                    stackList.push(topNum);
                }
                stackList.push(2);
            }
        }
        return stackList.isEmpty();
    }
}

     obviously , We can see that the effect of stack method is ok , At the same time, we can also use the method of in and out . First, divide the string by English comma to get an array , Initialize a tag value . Start traversing the circular array , Subtract the tag value 1, Then judge whether the tag value is less than 0, If yes, it will directly return the result of no . Judge again Whether the current character value is not equal to ’#' Value , If yes, add the tag value 2, Follow this idea to cycle until the end of traversal , Finally, judge whether the tag value is equal to 0, And return the judgment result . So according to this idea, we can solve , Here is Python Code ：

# Fire breathing dragon and water arrow turtle 
class Solution(object):
    def isValidSerialization(self, preorder):
        vex = preorder.split(',')
        resNum = 1
        for v in vex:
            resNum = resNum - 1
            if(resNum < 0):
                return False
            if(v != '#'):
                resNum = resNum + 2
        return resNum == 0

     As a result Java The efficiency of the stack method of version is ok , and Python The speed of the in and out method of version is also good , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .