“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”
Topic request
One way to serialize a binary tree is to use a pre-order traversal. When we encounter a non-empty node, we can record the value of the node. If it is an empty node, we can record it with a token value, such as #.
For example, the binary tree can be serialized as string above “4, 9 #, # 1, #, #, 2 #, 6, #, #”, where # represents a blank nodes.
Given a comma-separated sequence, verify that it is the correct preserialization 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 assume that the input format is always valid; for example, it will never contain two consecutive commas, such as “1, 3”.
Example 1:
Input: "9,3,4,#,#,1,#,#,2,#,6,#,#" output: trueCopy the codeExample 2:
Input: "1,#" Output: falseCopy the codeExample 3:
Input: "9,#,#,1" Output: falseCopy the codeStack method (assuming slots)
We can treat each node as a slot waiting to be filled. If the node is empty, a slot is consumed.
If the node is a non-empty node, two new slots are created when one slot is consumed. The root node needs special treatment.
We use stacks to maintain slot changes. Each element in the stack represents the number of slots left, and the top element represents the number of slots available for the next step. The top element is -1 when an empty node is encountered, and -1, +2 when a non-empty node is encountered. As long as the top element of the stack is 0, we can exit the stack.
If the stack is empty after the traversal, no slots need to be filled. Is a legal sequence. Otherwise, it is invalid. If the number of slots is insufficient during traversal, it is also invalid.
var isValidSerialization = function (preorder) { let arr = preorder.split(','); let stack = [1]; for (let i = 0; i < arr.length; i++) { const item = arr[i]; if (! stack.length) return false; const len = stack.length; if (item == "#") { stack[len - 1]--; if (stack[len - 1] == 0) stack.pop() } else { stack[len - 1]--; if (stack[len - 1] == 0) stack.pop() stack.push(2) } } return stack.length == 0 };Copy the codeUpgrade in slot mode
In the above method, we treat the slots of each node as independent, if we treat all the slots as a whole. Maintain all slot number changes with a single element.
var isValidSerialization = function (preorder) { const arr = preorder.split(","); const len = arr.length; // A slot is initialized by default. If it is an empty list ["#"], it will consume another slot. let slots = 1; for (let i = 0; i < len; i++) { if (slots == 0) return false; if (arr[i] == "#") { slots-- } else { slots++ } } return slots === 0 };Copy the codeBinary tree property method
According to the characteristics of the pre-order traversal, the order of root → left → right is traversed, and the right subtree is traversed only after all the left subtrees of the root node are traversed. So we can determine whether the left subtree is valid, and then whether the right subtree is valid. Finally, judge the root node. Let’s do it recursively. Here is how to determine whether a subtree is valid. First we need to find the deepest node, the leaf node, which is the node where both the left and right subtrees are “#”. So if we walk to the leaf node, we prove that we are walking to the last layer, and if this node is true, we can empty this node to determine whether the root node is also true. That is, use “#” to replace the leaf node. Replace 4## with #.
"9 and 4, #, # 1, #, #, 2 #, 6, #, #""1, 3, 9 #, #, #, and 2, #, 6, #, #""2, 3, 9 #, #, #, 6, #, #""9, # 2, # 6, #, #""9, # 2, #, #""#, 9 #,""#"
As above
var isValidSerialization = function (preorder) { const arr = preorder.split(","); const len = arr.length; let stack = []; for (let i = 0; i < len; i++) { stack.push(arr[i]) while (stack.length >= 3 && stack[stack.length - 1] == "#" && stack[stack.length - 2] == "#" && stack[stack.length - 3] ! = "#") { stack.pop(), stack.pop(), stack.pop() stack.push('#') } } return stack.length == 1 && stack[0] == "#" };Copy the codeRecursive method
We still according to the characteristics of the pre-order traversal of the binary tree, we carry out a pre-order traversal to judge the number of nodes of the binary tree.
We start by splitting the given string into an array. The number of left and right child nodes is calculated and the number of root nodes is 1 to determine whether it is equal to the length of the array.
var isValidSerialization = function (preorder) {
const arr = preorder.split(",");
let isValid = true;
let len = dfs(0, arr);
return isValid && len == arr.length
function dfs(index, arr) {
if (index >= arr.length) {
isValid = false;
return 0
}
if (arr[index] == "#") return 1;
let leftLen = dfs(index + 1, arr);
let rightLen = dfs(index + 1 + leftLen, arr)
return 1 + leftLen + rightLen
}
};
Copy the codeBinomial tree rules, degrees in and degrees out
Since every non-empty node in a binary tree has two outdegrees, and empty nodes have no outdegrees, all nodes (except the root node) have an in degree.
We can use in and out to record the amount of “in” and “out” respectively. M and n indicate number of non-empty nodes and Number of empty nodes respectively.
Meanwhile, the final result of a qualified binary tree must satisfy in == out.
However, we can not only use the final in == out to judge whether it is legal or not. It is easy to give a counterexample: Consider advancing all the empty nodes of a legal sequence, so that the final result still satisfies in == out, but such a binary tree does not exist.
We also need some additional features that allow us to know in advance that a binary tree is illegal during traversal.
For example, we can start from the premise of qualified binary trees and mine the relationship between in and out and n and m during traversal.
The minimum ratio between m and N of a qualified binary tree is 1:2, which corresponds to such a shape:
4
/ \\
# #
Copy the codeIn the traversal process, the minimum ratio between m and n is 1:0, which actually corresponds to the property that the empty node in the binary tree always follows the non-empty node.
In other words, the number of empty nodes is greater than the number of non-empty nodes until the last node is reached.
Number of non-empty nodes >= Number of empty nodes is constant before traversal ends: m>= N
Then we adopt another technique, which is to add two “out degree” and one “in degree” for each “non-empty node” in the traversal process, and only add one “in degree” for each “empty node”. Regardless of whether each “non-empty node” actually corresponds to two child nodes.
var isValidSerialization = function (preorder) { const arr = preorder.split(","); const len = arr.length; let enter = 0, out = 0; for (let i = 0; i < len; i++) { if (arr[i] ! = "#") out += 2; if (i ! = 0) enter++; if (i ! = (len - 1) && out <= enter) return false } return enter == out };Copy the codeSince in is a special character in JavaScript, we use Enter instead.