331. Verify Preorder Serialization of a Binary Tree

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

Intuition

2 # pop a node, and push this node into stack as another #

Code

public boolean isValidSerialization(String preorder) {
    if (preorder == null) {
        return false;
    }

    Stack<String> stack = new Stack<>();
    String[] nodes = preorder.split(",");

    for (int i = 0; i < nodes.length; i++) {

        String curr = nodes[i];
        while (curr.equals("#") && !stack.isEmpty() && stack.peek().equals(curr)) {
            stack.pop();
            if (stack.isEmpty()) {
                return false;
            }
            stack.pop();
        }
        stack.push(curr);
        System.out.println(stack.toString());
    }

    return stack.size() == 1 && stack.peek().equals("#");
}

Complexity

• Time: O(N)
• Space: O(N)

---

Solution 2

Intuition

Code

Complexity

• Time:
• Space:

---

Similar Questions