Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/331.html
One way to serialize a binary tree is to use preorder traversal. When we encounter a nonnull 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 commaseparated values preorder
, return true
if it is a correct preorder traversal serialization of a binary tree.
It is guaranteed that each commaseparated 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.
Example 1:
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true
Example 2:
Input: preorder = "1,#" Output: false
Example 3:
Input: preorder = "9,#,#,1" Output: false
Constraints:
1 <= preorder.length <= 10^{4}
preorder
consist of integers in the range[0, 100]
and'#'
separated by commas','
.
Algorithm
 The number of digits is always one less than
#
 The last one must be
#
 leaf node:
number, #, #
If we initialize a counter to 0,
 When a number is encountered, the counter increases by 1,
 When the # sign is encountered, the counter is decreased by 1, Then the counter should still be 0 at the end.
Two examples that return False, #,7,6,9,#,#,#
and 7,2,#,2,#,#,#,6,#
, then through these two counter examples,
 If the root node is empty, there can be no more nodes behind,
 And there cannot be three consecutive
#
signs.
So when we add or subtract the counter, if we encounter the #
number, and the counter is already 0, and then subtracted to become a negative number, we directly return False, because in the correct sequence, any position i is in [ 0, i]
The number of # numbers in the range is not greater than the number of digits.
When the loop is complete, we check whether the counter is 0 and also see whether the last character is #
sign.
Code

import java.util.Stack; public class Verify_Preorder_Serialization_of_a_Binary_Tree { // https://leetcode.com/problems/verifypreorderserializationofabinarytree/discuss/78551/7linesEasyJavaSolution public class Solution_noStack { public boolean isValidSerialization(String preorder) { String[] nodes = preorder.split(","); int diff = 1; // if single node tree [root] for (String node: nodes) { if (diff < 0) return false; if (!node.equals("#")) diff += 2; } return diff == 0; } } public class Solution { public boolean isValidSerialization(String preorder) { if (preorder == null  preorder.length() == 0) { return true; } String[] nodes = preorder.split(","); Stack<String> stack = new Stack<>(); for (String node : nodes) { if (node.equals("#")) { // after first while loop, current node can be deemed as # while (!stack.isEmpty() && stack.peek().equals("#")) { stack.pop(); // pop # in stack if (stack.isEmpty()) { // should leave a number in stack return false; } stack.pop(); // pop val with left# and right# => repalce it with # } } stack.push(node); } return stack.size() == 1 && stack.peek().equals("#"); } } } ############ class Solution { public boolean isValidSerialization(String preorder) { String[] strs = preorder.split(","); int diff = 1; for (String s : strs) { if (diff < 0) { return false; } if (!s.equals("#")) { diff += 2; } } return diff == 0; } }

class Solution { public: bool isValidSerialization(string preorder) { istringstream in(preorder); vector<string> v; string t = ""; int cnt = 0; while (getline(in, t, ',')) v.push_back(t); for (int i = 0; i < v.size()  1; ++i) { if (v[i] == "#") { if (cnt == 0) return false; cnt; } else ++cnt; } return cnt == 0 && v.back() == "#"; } }; class Solution { public: bool isValidSerialization(string preorder) { int capacity = 1; preorder += ","; for (int i = 0; i < preorder.size(); ++i) { if (preorder[i] != ',') continue; if (capacity < 0) return false; if (preorder[i  1] != '#') capacity += 2; } return capacity == 0; } };

''' In this solution, we split the input string by comma to get a list of nodes. We then initialize the indegree counter to 1 for the root node, since the root has no incoming edges. We then loop through the nodes and for each node, we decrease the indegree counter by 1. If the indegree counter becomes negative, it means that there are more incoming edges than expected, and the tree is invalid. In this case, we return False. If the current node is not null (i.e., not '#'), we increase the indegree counter by 2 for its two children. This is because every nonnull node has two children in a binary tree. Finally, we return True if the final indegree counter is 0, meaning that all incoming edges have been accounted for. ''' class Solution: def isValidSerialization(self, preorder: str) > bool: # Split the string by comma to get the list of nodes nodes = preorder.split(',') # since the root has no incoming edges indegree = 1 for node in nodes: # Decrease the indegree for the current node indegree = 1 # If the indegree is negative, return False because the tree is invalid if indegree < 0: return False # If the current node is not null, increase the indegree by 2 for its children if node != '#': indegree += 2 # Return True if the final indegree is 0 return indegree == 0 ############ class Solution: def isValidSerialization(self, preorder: str) > bool: if not preorder: return True nodes = preorder.split(",") stack = [] for node in nodes: if node == "#": # after first while loop, current node can be deemed as # while stack and stack[1] == "#": stack.pop() # pop # in stack if not stack: # should leave a number in stack return False stack.pop() # pop val with left# and right# => repalce it with # stack.append(node) return len(stack) == 1 and stack[0] == "#"