preface
Yesterday wrote an answer key is [LeetCode94 title sequence in the binary tree traversal] brush | punch, the antithesis to everybody simple introduced the binary tree traversal ways, why call before the order, in sequence, after the sequence traversal, interested or want to know can go to see the 😄 😄 😄
Topic describes
Verify the sequential serialization of the binary tree
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 #.
_9_ / / 2/3/4 1 # 6 / \ \ / \ \ # # # # # #Copy the codeFor 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 codeTheir thinking
Verify that preorder is the correct sequential serialization of the binary tree and cannot reconstruct the tree.
In a tree, the sum of the inputs of all nodes is equal to the sum of the outputs. So we can determine if the input sequence is valid based on this feature!
In a binary tree:
1. Each empty node (“#”) provides 0 out degree and 1 in degree.
2. Each non-empty node provides two out degrees and one in degrees.
So, we first convert preorder to the array Nodes and define a dif = 1 to calculate the degree.
When we add a non-empty node, we always subtract an in degree and add two out degrees. But since the root node has no parent, its degree of entry is 0 and its degree of exit is 2. So the diff is initialized to 1 so that when you add the root node, you subtract an in and add two outs, and the diff should be exactly 2.
To verify the binary tree preorder, you iterate over nodes, each adding dif = out – in. When traversing any node, dif is required to be greater than 0, because the node’s children have not been traversed, so the out degree should be greater than or equal to the in degree. When all nodes are traversed, the dif of the whole tree === 0.
The problem solving code
/** * @param {string} preorder * @return {boolean} */ var isValidSerialization = function(preorder) { let nodes = preorder.split(','); let dif = 1; for (node of nodes) { dif -= 1; if (dif < 0) { return false; } if (node ! == '#') { dif += 2; } } return dif === 0; };Copy the codeSwipe questions and punch out records
Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏
[LeetCode0303 topic area and retrieval – array immutable] | punch brush
[LeetCode1200. Minimum absolute difference] | punch brush
[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush
[LeetCode11 topic containers of most water] | punch brush
[LeetCode0338 topic bit count] | punch brush
[LeetCode209 topic length minimum subarray] | punch brush
[LeetCode236 topic in recent common ancestor of binary tree] | punch brush
[LeetCode141 topic circular linked list] | punch brush
[LeetCode53 topic most architectural sequence and] | punch brush
[LeetCode48 topic rotating images] | punch brush
[LeetCode155 topic minimum stack] | punch brush
[LeetCode1124 problem well, the longest period of a] | punch brush
[LeetCode274 problem H index] | punch brush
[LeetCode367 problem effective completely square number] | punch brush
[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush
[LeetCode160 topic cross linked list] | punch brush
[LeetCode1438 topic absolute difference does not exceed the limit of the longest continuous subarray] | punch brush
[LeetCode434 problem the number of words in a string] | punch brush
[LeetCode75 topic classification of color] | punch brush
[LeetCode513 problem to find the value of the trees left] | punch brush
[LeetCode94 title sequence in the binary tree traversal] | punch brush
[LeetCode617 topic merger binary tree] | punch brush
conclusion
Come on! HXDM!!!!!! 💪 💪 💪
This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign