Dare2Solve
The problem asks to determine whether a given preorder
traversal string represents a valid serialization of a binary tree. The nodes in the tree are represented by integers and nulls, where null nodes are represented by #
and the nodes are separated by commas.
A valid serialization must accurately represent a binary tree, with non-null nodes having exactly two children (either null or non-null), and null nodes indicating the absence of a subtree.
The idea is to use a balance counter to represent the difference between the number of non-null nodes that expect child nodes and the number of child nodes provided by null nodes or subsequent non-null nodes.
preorder
string (split by commas):
#
), decrease the balance as it fills one child node slot.preorder
string.class Solution {
public:
bool isValidSerialization(string preorder) {
int balance = 1;
stringstream ss(preorder);
string node;
while (getline(ss, node, ',')) {
if (balance <= 0) return false;
if (node == "#") --balance;
else ++balance;
}
return balance == 0;
}
};
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
balance = 1
for node in preorder.split(','):
if balance <= 0:
return False
if node == '#':
balance -= 1
else:
balance += 1
return balance == 0
class Solution {
public boolean isValidSerialization(String preorder) {
int balance = 1;
String[] nodes = preorder.split(",");
for (String node : nodes) {
if (balance <= 0) return false;
if (node.equals("#")) balance--;
else balance++;
}
return balance == 0;
}
}
/**
* @param {string} preorder
* @return {boolean}
*/
var isValidSerialization = function (preorder) {
let balance = 1
for (const node of preorder.split(','))
if (balance > 0)
if (node === '#') --balance
else ++balance
else return false
return balance < 1
}