# 331    Verify Preorder Serialization of a Binary Tree

## 331. [Verify Preorder Serialization of a Binary Tree](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/)

## 1. Question

One way to serialize a binary tree is to use pre-order 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`#`.

```
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
```

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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

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"`.

**Example 1:**`"9,3,4,#,#,1,#,#,2,#,6,#,#"`\
Return`true`

**Example 2:**`"1,#"`\
Return`false`

**Example 3:**`"9,#,#,1"`\
Return`false`

## 2. Implementation

**(1) Stack**

思路: 这里用stack和利用stack做preorder traversal类似，可以分以下几种情况考虑:

1. 如果当前的node是数字，说明我们将以这个node作为根展开，将node push到stack
2. 如果当前的node是#,

2.1. 而栈顶是数字，说明当前的node代表的是left null child,我们将它放在stack上作为一个记号，这样接下来node就知道它自己是right child

2.2. 而栈顶是#，说明当前node是right null child, 这时我们至少call两次 stack.pop()，代表以node的parent作为根的subtree cancel，同时我们查看栈顶的是数字还是#

2.2.1. 如果栈顶是数字，说明我们刚刚将一个node t从栈顶弹出，而这个node t是一个left child, 这时我们需要将#留在stack里，作为记号，让后面的node知道它自己是right child

2.2.2 如果栈顶是#, 说明我们刚刚取消了一个以node t为根的subtree, 而node t是一个right child，所以我们继续将stack元素弹出

```java
class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return false;
        }

        String[] nodes = preorder.split(",");

        Stack<String> stack = new Stack<>();

        for (String node : nodes) {
            while (node.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
                stack.pop();

                if (stack.isEmpty()) {
                    return false;
                }

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

**(2) Graph Property**

思路: 这种解法利用了树的入度和出度是相同的性质。我们定义diff = Outdegree - Indegree, 对于每个node，其入度为1，所以diff也相应减1。而如果node不是#的话，出度为2，所以diff也相应加2。需要注意的是，我们将diff初始化为1,原因是我们将root也作为一个普通的node处理，然而root的入度是0， 出度是2，所以我们将diff初始化为1，这样root作为普通node，它的diff也是1

```java
class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return false;
        }

        String[] nodes = preorder.split(",");

        int diff = 1;
        for (String node : nodes) {
            --diff;
            if (diff < 0) {
                return false;
            }
            if (!node.equals("#")) {
                diff += 2;
            }
        }
        return diff == 0;
    }
}
```

## 3. Time & Space Complexity

**Stack:** 时间复杂度O(n), 空间复杂度O(n)

**Graph Property** : 时间复杂度O(n), 空间复杂度O(1)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/stack/331-verify-preorderserialization-of-a-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.