刷题

一、题目描述：

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
注意：不允许重建树。

示例 1:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:

输入: preorder = "1,#"
输出: false
示例 3:

输入: preorder = "9,#,#,1"
输出: false

提示:

1 <= preorder.length <= 104
preorder 由以逗号 “，” 分隔的 [0,100] 范围内的整数和 “#” 组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

二叉树是图的一种，由于前序遍历是先访问根节点，所以在遍历序列过程中，出度-入度>0，遍历完成后出度=入度；
将非空节点的入度设为1，出度设为2，空节点的入度设为1，出度设为0.
扫描字符串，计算累加出度和（in）以及入度和(out)，如果中途出现入度和（in）大于出度和（out）的情况,说明不满足二叉树的先序序列。扫描结束后out不等于in,不满足图的性质，更不符合二叉树的性质。

三、AC 代码：

class Solution {
    public boolean isValidSerialization(String preorder) {
        int indegree = 0, outdegree = 0;
        String[] ss = preorder.split(",");
        if (ss.length <= 0) {
            return true;
        }
        if (ss[0].trim().equals("#") && ss.length != 1) {
            return false;
        }
        for (int i = 0; i < ss.length; i++) {
            String s = ss[i];
            s = s.trim();
            indegree++;
            if (indegree - outdegree > 1) {
                return false;
            }
            if (!s.equals("#")) {
                outdegree += 2;
            }
        }
        return indegree - outdegree == 1;
    }
}