Subject to introduce

Force buckle 331: leetcode-cn.com/problems/ve…

Analysis of the

Using binary treesThe out is equal to the inTo judge the condition of.

If there is A directed edge A -> B, then this edge adds an out degree to A and an in degree to B.

A binary tree is a graph, a directed graph, a directed edge brings in an input and an output, and the total input of a binary tree is equal to the total output, which is also equal to the number of edges. That is, at the end of the iteration, the total in must be equal to the total out

During traversal (null is also considered a node) :

  • The root node provides two outputs
  • A real node, other than the root node, provides 2 out degrees and 1 in degrees
  • The NULL node provides one entry

Before we get to the end? There will definitely be no in >= out moment. Why is that?

  • Looking at Figure 1, providing one exit degree can be interpreted as providing a mount point, and providing one entry degree as consuming a mount point

  • In >= Out: Indicates that the mount points consumed by the traversed nodes are greater than or equal to the provided mount points

  • The following node cannot be mounted, but the node is full, which is illegal.

If you walk through a binary tree (null is also a node), the branches that you walk through must not be full, or you will not walk to the next node, and when you walk to the last node, they will be full.

The code is as follows:

class Solution {
    public boolean isValidSerialization(String preorder) {
        // Start by separating according to English comma
        String[] dataArr=preorder.split(",");
        List<String> dataList= Arrays.asList(dataArr);
        return  preOrder(dataList);
    }

    public boolean preOrder(List<String> dataList) { 
        // Out, in, out
        int out=0,in=-1;
        for(int i = 0; i < dataList.size(); i++){// The input degree is 1
            in++;
            // If the input degree is greater than the output degree, return false
            if(out < in) {
                return false;
            }
            if(! dataList.get(i).equals("#")) {
                // The output degree is 2
                out+=2; }}returnout == in; }}Copy the code