[数据结构与算法]331.验证二叉树的前序序列化

331. 验证二叉树的前序序列化

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

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

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

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

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,3” 。

示例 1:
输入: “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true

示例 2:
输入: “1,#”
输出: false

示例 3:
输入: “9,#,#,1”
输出: false

来自 https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/

方法一：栈

槽位：

一个槽位可以看作是二叉树中待填充的位置

具体：

1. 当遇到空节点时，要消耗一个槽位，槽位数量-1
因为空节点没有子节点
2. 当遇到非空节点时，要消耗一个槽位，且新增加了两个槽位
因为非空节点有两个子节点（子节点可能空也可能非空）

结合题目：

使用栈来维护槽位的变化
1. 当遇到空节点时，栈顶槽位数-1
2. 当遇到非空节点时，栈顶槽位数-1，再压入一个槽位数为2的

遍历结束后，若栈为空，说明槽位都填满了，合法
若栈非空，序列不合法
遍历过程中，若槽位不足，则序列不合法

代码

class Solution {
    public boolean isValidSerialization(String preorder) 
    {
        String[] c=preorder.split(",");
        if(c[0].equals("#")&&c.length==1)
        {
            return true;
        }
        if(c[0].equals("#")&&c.length!=1)
        {
            return false;
        }
        Deque<Integer> d=new LinkedList<>();
        d.push(2);
        for(int i=1;i<c.length;i++)
        {
            //System.out.println(d.peek());
            if(d.isEmpty())
            {
                return false;
            }
            int peek=d.poll();
            if(peek!=1)
            {
                d.push(--peek);
            }
            if(!c[i].equals("#"))
            {
                d.push(2);
            }
        }
        if(d.isEmpty())
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

注意

1. split方法返回的是一个String数组
2. String类型的和"…"比较时，不能用==，得用equals方法

优化

计数：

只用一个值计算槽位数