2024.3.31力扣每日一题——验证二叉树的前序序列化

题目来源

力扣每日一题；题序：331

我的题解

方法一 计数

• 当只有一个节点并且是空节点，则表示是空树，是一个正确的序列化
• 正确的序列化节点数必然是偶数个，若不是偶数个，则不是一个正确的序列化
• 除了空树起始节点必然不可能是空节点
• 一个正确的序列化，必然非空节点数量比空节点数量少1

时间复杂度：O(n)
空间复杂度：O(1)

public boolean isValidSerialization(String preorder) {
    //空树
    if(preorder.equals("#"))
        return true;
    String[] s=preorder.split(",");
    int n=s.length;
    //包含空节点的树必然有偶数个节点   除了空树起始节点必然不可能是空节点
    if(n%2==0||s[0].equals("#"))
        return false;
    int countNum=0;
    int countChar=0;
    for(int i=0;i<n;i++){
        String s1=s[i];
        if(!s1.equals("#")){
            countNum++;
        }else{
            countChar++;
        }
        //若前面已经是一个完整的树，后序还有节点，则必然不是一个有效的树的前序序列化
        if(i<n-1&&countChar==countNum+1)
            return false;

    }
    //树的非空节点数必然比空节点少一个
    if(countChar!=countNum+1)
        return false;
    
    return true;
}

方法二 栈

参考官方题解

时间复杂度：O(n)
空间复杂度：O(1)

public boolean isValidSerialization(String preorder) {
    int n = preorder.length();
    int i = 0;
    Deque<Integer> stack = new LinkedList<Integer>();
    stack.push(1);
    while (i < n) {
        if (stack.isEmpty()) {
            return false;
        }
        if (preorder.charAt(i) == ',') {
            i++;
        } else if (preorder.charAt(i) == '#'){
            int top = stack.pop() - 1;
            if (top > 0) {
                stack.push(top);
            }
            i++;
        } else {
            // 读一个数字
            while (i < n && preorder.charAt(i) != ',') {
                i++;
            }
            int top = stack.pop() - 1;
            if (top > 0) {
                stack.push(top);
            }
            stack.push(2);
        }
    }
    return stack.isEmpty();
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~