LeetCode_Stack_331. Verify Preorder Serialization of a Binary Tree (Java) [stack, string processing]

catalogue

1, Title Description

English description

Chinese description

Examples and descriptions

2, Problem solving ideas

1. Stack merge node

2. Calculate the input and output

3, AC code

Java

Stack

Calculate access

 

4, Problem solving process

First Bo

Second stroke

 

1, Title Description

English description

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.


For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

 

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid.

For example, it could never contain two consecutive commas, such as "1,,3".
Note: You are not allowed to reconstruct the tree.

Chinese description

One way to serialize a binary tree is to use preorder traversal. When we encounter a non empty node, we can record the value of this node. If it is an empty node, we can use a tag value record, for example #.


For example, the above binary tree can be serialized into the string "9,3,4, #, #, 1, #, #, 2, #, 6, #, #, #", where # represents an empty node.

Given a comma separated sequence, verify that it is the correct preamble serialization of the binary tree. Write a feasible algorithm without reconstructing the tree.

Each comma separated character is either an integer or a '#' representing a null pointer.

You can think that the input format is always valid. For example, it will never contain two consecutive commas, such as "1,, 3".

Examples and descriptions

Source: LeetCode
Link: https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.  

 

2, Problem solving ideas

1. Stack merge node

The idea of the algorithm is very simple. It is directly shown in the figure above:

One leaf node + two empty nodes} is transformed into an empty node from bottom to top until it is finally simplified into an empty node.

2. Calculate the input and output

reference resources @Negative snow candlelight [two solutions to the astonishment of the table: "stack" and "in and out"]

 

 

3, AC code

Java

Stack

class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] tree = preorder.split(",");
        Deque<String> record = new LinkedList<>();
        for (int i = 0; i < tree.length; i++) {
            if (!tree[i].equals("#")) record.push(tree[i]);
            else {
                if (!record.isEmpty() && record.peek().equals("#")) {
                    while (!record.isEmpty() && record.peek().equals("#")) {
                        if (record.size() < 2) return false;
                        record.pop();
                        record.pop();
                    }
                    record.push("#");
                } else record.push(tree[i]);
            }
            // System.out.println("----------------");
            // System.out.println(record.toString());
        }
        return record.size() == 1 && record.peek().equals("#");
    }
}

// Another more concise implementation
class Solution {
    public boolean isValidSerialization(String preorder) {
        LinkedList<String> stack = new LinkedList<>();
        for (String s : preorder.split(",")) {
            stack.push(s);
            while (stack.size() >= 3
                    && stack.get(0).equals("#")
                    && stack.get(1).equals("#")
                    && !stack.get(2).equals("#")) {
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        return stack.size() == 1 && stack.pop().equals("#");
    }
}

Calculate access

// Wrong implementation method, for example, test cases are "#, 7,6,9, #, #, #, #"
// class Solution {
//     public boolean isValidSerialization(String preorder) {
//         String[] tree = preorder.split(",");
//         int diff = 1;
//         for (int i = 0; i < tree.length; i++) {
//             if (tree[i].equals("#")) {
//                 diff -= 1;
//                 if (diff < 0) return false;
//             } else {
//                 diff += 1;
//             }
//             System.out.println(diff);
//         }
//         return diff == 0;
//     }
// }


class Solution {
    public boolean isValidSerialization(String preorder) {
        int diff = 1;
        for(String s : preorder.split(",")){
            diff--;// This method of directly subtracting one followed by normal nodes plus two can skillfully deal with the use cases where the header node is empty
            if (diff < 0){
                return false;
            }
            if(!s.equals("#")){
                diff += 2;
            }
        }
        return diff == 0;
    }
}

 

4, Problem solving process

First Bo

The teacher talked about the method of using stack in class. The details have been adjusted for a long time

 

Second stroke

In the problem solution, we see a more concise method to calculate the input and output. For this problem, the sum of degrees is equal to the sum of degrees

 

Keywords: leetcode tree stack

Added by inkel on Sun, 26 Dec 2021 15:13:38 +0200