catalogue
2. Calculate the input and output
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
