LeetCode 0331. Verify Preorder Serialization of a Binary Tree Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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.

• 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 <= 104
• preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Solutions

Solution 1: Stack

We split the string preorder into an array by commas, then traverse the array. If we encounter two consecutive '#' and the third element is not '#', we replace these three elements with a single '#'. This process continues until the array traversal is complete.

Finally, we check whether the length of the array is 1 and whether the only element in the array is '#'.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the string preorder.

PythonJavaC++GoTypeScript

class Solution: def isValidSerialization(self, preorder: str) -> bool: stk = [] for c in preorder.split(","): stk.append(c) while len(stk) > 2 and stk[-1] == stk[-2] == "#" and stk[-3] != "#": stk = stk[:-3] stk.append("#") return len(stk) == 1 and stk[0] == "#"(code-box)

class Solution { public boolean isValidSerialization(String preorder) { List<String> stk = new ArrayList<>(); for (String s : preorder.split(",")) { stk.add(s); while (stk.size() >= 3 && stk.get(stk.size() - 1).equals("#") && stk.get(stk.size() - 2).equals("#") && !stk.get(stk.size() - 3).equals("#")) { stk.remove(stk.size() - 1); stk.remove(stk.size() - 1); stk.remove(stk.size() - 1); stk.add("#"); } } return stk.size() == 1 && stk.get(0).equals("#"); } }(code-box)

class Solution { public: bool isValidSerialization(string preorder) { vector<string> stk; stringstream ss(preorder); string s; while (getline(ss, s, ',')) { stk.push_back(s); while (stk.size() >= 3 && stk[stk.size() - 1] == "#" && stk[stk.size() - 2] == "#" && stk[stk.size() - 3] != "#") { stk.pop_back(); stk.pop_back(); stk.pop_back(); stk.push_back("#"); } } return stk.size() == 1 && stk[0] == "#"; } };(code-box)

func isValidSerialization(preorder string) bool { stk := []string{} for _, s := range strings.Split(preorder, ",") { stk = append(stk, s) for len(stk) >= 3 && stk[len(stk)-1] == "#" && stk[len(stk)-2] == "#" && stk[len(stk)-3] != "#" { stk = stk[:len(stk)-3] stk = append(stk, "#") } } return len(stk) == 1 && stk[0] == "#" }(code-box)

function isValidSerialization(preorder: string): boolean { const stk: string[] = []; for (const s of preorder.split(',')) { stk.push(s); while (stk.length >= 3 && stk.at(-1) === '#' && stk.at(-2) === '#' && stk.at(-3) !== '#') { stk.splice(-3, 3, '#'); } } return stk.length === 1 && stk[0] === '#'; }(code-box)