Sponsored
Sponsored
The idea is to track available slots in the binary tree. Initially, we start with one slot for the root. For each node, we consume a slot. If the node is non-null, it adds two more slots (one for each child). A null node ('#') does not add any slots. The binary tree is valid if, at the end of processing all nodes, all slots are exactly filled (i.e., zero slots remaining).
Time Complexity: O(n), where n is the length of the preorder string, as we are iterating through the nodes once.
Space Complexity: O(1), with no additional data structures used.
1using System;
2
3public class Solution {
4 public bool IsValidSerialization(string preorder) {
5 int slots = 1;
6 string[] nodes = preorder.Split(',');
7 foreach (string node in nodes) {
8 slots--;
9 if (slots < 0) return false;
10 if (node != "#") slots += 2;
11 }
12 return slots == 0;
13 }
14
15 public static void Main() {
16 Solution solution = new Solution();
17 string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
18 Console.WriteLine(solution.IsValidSerialization(preorder));
19 }
20}This C# code follows the same principle using string manipulation and slot management logic to ensure that the given serialization is valid.
This approach involves simulating a stack-based tree traversal. The idea is to treat each "open bracket" as requiring nodes and each "close bracket" as completing them. We aim to manage the state of openings and closures using integers, representing how many nodes are expected at any point in the traversal.
Time Complexity: O(n), parsing each node once.
Space Complexity: O(1), with only integer variables used for tracking.
public class Solution {
public bool IsValidSerialization(string preorder) {
int diff = 1;
string[] nodes = preorder.Split(',');
foreach (string node in nodes) {
if (--diff < 0) return false;
if (node != "#") diff += 2;
}
return diff == 0;
}
public static void Main() {
Solution solution = new Solution();
string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
Console.WriteLine(solution.IsValidSerialization(preorder));
}
}C# version splits strings and implements differential management similarly to stack-based approach but through simple arithmetic.