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

题目

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

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

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

保证 每个以逗号分隔的字符或为一个整数或为一个表示 $null$ 指针的 ${}^{\prime }{\#}^{\prime }$ 。

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

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

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

示例 2:
输入: $preorder="1,\#"$
输出: $false$

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

提示:

• $1\le preorder.length\le 10^4$
• $preorder$ 由以逗号 $"，"$ 分隔的 $[0,100]$ 范围内的整数和 $“\#”$ 组成

思路

这道题要求验证给定的序列是否是正确的二叉树的前序序列化，而且不能重建树。可以使用迭代的方法来模拟整个过程。

可以观察到一个有效的二叉树序列化中，非空节点后面必然跟着两个${}^{\prime }{\#}^{\prime }$表示空节点，因为二叉树中的每个节点都有两个子节点（包括空节点）。所以可以遍历序列，当遇到一个非空节点时，记录之后的两个节点是否为${}^{\prime }{\#}^{\prime }$，如果是则继续遍历，否则返回$false$。遍历完成后，如果指针指向了序列的末尾，则返回$true$，否则返回$false$。

代码

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int p = 0;
        return dfs(preorder, p) && p == preorder.size();
    }

    bool dfs(const string& preorder, int& p) {
        if (p == preorder.size()) {
            return false;
        }

        if (preorder[p] == '#') {
            if (p == preorder.size() - 1) p++;
            else p += 2;
            return true;
        }

        while (p < preorder.size() && preorder[p] != ',') p++;

        if (p == preorder.size()) return false;

        p += 1;

        return dfs(preorder, p) && dfs(preorder, p);
    }
};

复杂度分析

时间复杂度

遍历整个序列，时间复杂度为$O(n)$

空间复杂度

递归调用的深度最坏情况下为$O(n)$

结果

总结

使用了递归的方法，通过模拟二叉树的前序遍历来判断序列是否有效。