# 0331. Verify Preorder Serialization of a Binary Tree

<https://leetcode.com/problems/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 `'#'`.

![](https://assets.leetcode.com/uploads/2021/03/12/pre-tree.jpg) 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 `','`.

## ac1: preorder offset each node

<https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78566/Java-intuitive-22ms-solution-with-stack/83378>

* See number, push to stack;
* See #:
  * stack top is number, it's left null child, push to stack;
  * stack top is #, it's right null child. Cancel a subtree by `pop()` twice. Keep doing this.
* Finally, only one # is left in the stack.

```java
class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < nodes.length; i++) {
            if ("#".equals(nodes[i])) {
                while (!stack.isEmpty() && stack.peek().equals("#")) {
                    stack.pop();
                    if (stack.isEmpty()) return false;
                    stack.pop();
                }
            }
            stack.push(nodes[i]);
        }

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

## ac2: count leaves and non-leaves

<https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution/83320>

If we treat null's as leaves, then the binary tree will always be full. A full binary tree has a good property that `# of leaves = # of nonleaves + 1`

```java
class Solution {
    public boolean isValidSerialization(String preorder) {
        int leaves = 0, nonLeaves = 0;
        for (String s : preorder.split(",")) {
            // Got a complete full tree before running out of nodes, which is invalid.
            if (leaves == nonLeaves + 1) return false;
            if ("#".equals(s)) {
                leaves++;
            } else {
                nonLeaves++;
            }
        }

        return leaves == nonLeaves + 1;
    }
}
```

## ac3: count in-degree and out-degree

<https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution>

This is rediculous for interview.

```java
class Solution {
    public boolean isValidSerialization(String preorder) {
        int in = 0;
        int out = 1; // This is to account for root node, which has no in-degree.
        for (String s : preorder.split(",")) {
            in++;
            // In-degree > out-degree: the new node cannot link to a parent node(No one is providing out-degree for it).
            if (in > out) return false;

            if (!"#".equals(s)) {
                out += 2;
            }
        }

        return in == out;
    }
}
```