One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null 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 comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.
It is guaranteed that each comma-separated 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.
"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 <= 104preorder consist of integers in the range [0, 100] and '#' separated by commas ','.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).
The code uses strtok to tokenize the input string by commas. It starts with 1 available slot and decrements the slot count for each node. Non-null nodes (integers) add two slots, while null nodes ('#') simply use up a slot. If slots go negative at any point, the serialization is invalid. Finally, check all slots are used up.
C++
Java
Python
C#
JavaScript
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.
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.
This C code uses strtok for splitting and maintains a count 'diff' (similar to slots) decrementing for nodes and adjusting according to whether nodes are null or not.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), parsing each node once.
Space Complexity: O(1), with only integer variables used for tracking.
| Approach | Complexity |
|---|---|
| Using Slot Management | Time Complexity: O(n), where n is the length of the preorder string, as we are iterating through the nodes once. |
| Simulate Stack-Based Preorder Traversal | Time Complexity: O(n), parsing each node once. |
Serialize and Deserialize Binary Tree - Preorder Traversal - Leetcode 297 - Python • NeetCode • 128,074 views views
Watch 9 more video solutions →Practice Verify Preorder Serialization of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor