LeetCode/solutions/331. Verify Preorder Serialization of a Binary Tree.md

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

# 思路
题目给定一个字符串，判断这个字符串能否表示成一个二叉树。

字符串中每个节点用逗号分割，所以我们可以先用`istringsteam`将这个字符串转换成输入流，然后用`getline`并设置分隔符delim为逗号（默认是换行符）不断获得每个节点node。
``` C++
istringstream in(preorder);
string node;
while(getline(in, node, ',')){
   .....
}
```

## 思路一

这题的分类是栈，我们可以用栈解决，参考[讨论区](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78566/Java-intuitive-22ms-solution-with-stack)。

开辟一个栈，然后不断检查获得的节点node，有两种情况:
1. node为一个数，说明接下来会开辟一个以这个节点为根的子树，所以我们将其压栈；
2. node为#，此时根据栈顶划分又有两种情况：
```
  2.1 栈顶为一个数，说明当前的#为左空节点，压栈就可以了（等待它的兄弟）。
  2.2 栈顶为#，说明当前#为右空节点，栈顶为其左兄弟，应该出栈两次将其左兄弟及父亲删除，
      然后回到第2.1开始不断循环，直到栈顶为一个数或者栈空，最后才将当前#入栈。
```
2.2中出栈两次是连贯的过程，所以如果第一次出栈后栈就空了则可以直接返回false。检查完毕后，如果栈中只剩下一个元素且就为#即可返回true，否则返回false。

以"9,3,4,#,#,1,#,#,2,#,6,#,#"为例的话上述过程如下图所示：
![](https://www.programcreek.com/wp-content/uploads/2016/04/verify-preorder-serialization-of-a-binary-tree-leetcode-java-730x468.jpg)

时空复杂度均为O(n)。

## 思路二
看[讨论区](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/discuss/78551/7-lines-Easy-Java-Solution)发现有一个不用栈的方法，常数时间复杂度。

在二叉树中，如果把空节点#当做是叶子，那么
* 所有非空节点有2个出度1个入度（除了根节点）；
* 所有空节点（即#）有0个出度1个入度。

我们维持一个变量diff代表 出度减去入度，初始为1（因为根节点入度为0而不是1）。遇到当前节点node时，先将diff减去1（因为不管node是否为空都有1个入度），
如果非空（即不是#），那还应该将diff加上2。这个过程中如果一旦遇到diff小于0则可返回false，最后返回 `diff==0`。

时间复杂度O(n), 空间复杂度O(1)。


# C++
## 思路一
``` C++
class Solution {
public:
    bool isValidSerialization(string preorder) {  
        istringstream in(preorder);
        string node;
        
        stack<char>stk;
        while(getline(in, node, ',')){
            if(node != "#") stk.push('n');
            else{
                while(!stk.empty() && stk.top() == '#'){
                    stk.pop();
                    if (stk.empty()) return false;
                    stk.pop();
                }
                stk.push('#');
            }
        }
        return stk.size() == 1 && stk.top() == '#';
    }
};
```

## 思路二
``` C++
class Solution {
public:
    bool isValidSerialization(string preorder) {  
        istringstream in(preorder);
        string node;
        
        int diff = 1;
        while(getline(in, node, ',')){
            if (--diff < 0) return false;
            if (node != "#") diff += 2;
        }
        return diff == 0;
    }
};
```