Medium

题目描述

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

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

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

保证 输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= preorder.length <= 10^4
  • preorder 由整数（在范围 [0, 100] 内）和 '#' 组成，用逗号 ',' 分隔

解题思路

思路分析

这道题有两种主要解法：

方法一：度数统计法（推荐）

将二叉树看作图，每个节点最多有一个入度和两个出度。对于前序遍历：

  • 每个非空节点贡献 1 个入度（除了根节点）和 2 个出度
  • 每个空节点（#）贡献 1 个入度，0 个出度

整个过程中，出度应该始终 ≥ 入度，最后两者相等。我们可以用一个变量 diff = 出度 - 入度 来跟踪：

  • 遇到非空节点：diff += 1（+2出度-1入度，根节点无入度所以是+2）
  • 遇到空节点：diff -= 1（+0出度-1入度）
  • 过程中 diff 不能小于 0
  • 最终 diff 应该等于 0

方法二：栈模拟法

使用栈模拟递归构建过程，遇到连续的空节点时进行回溯。具体是将连续的"值,#,#“模式替换为单个”#"，直到无法继续替换。

度数统计法更简洁高效，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int diff = 1; // 出度 - 入度
        istringstream iss(preorder);
        string node;
        
        while (getline(iss, node, ',')) {
            diff--; // 每个节点都有入度（除了第一个根节点，但我们初始化为1来处理）
            if (diff < 0) return false;
            
            if (node != "#") {
                diff += 2; // 非空节点有两个出度
            }
        }
        
        return diff == 0;
    }
};

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        diff = 1  # 出度 - 入度
        nodes = preorder.split(',')
        
        for node in nodes:
            diff -= 1  # 每个节点都有入度
            if diff < 0:
                return False
            
            if node != '#':
                diff += 2  # 非空节点有两个出度
        
        return diff == 0

public class Solution {
    public bool IsValidSerialization(string preorder) {
        int diff = 1; // 出度 - 入度
        string[] nodes = preorder.Split(',');
        
        foreach (string node in nodes) {
            diff--; // 每个节点都有入度
            if (diff < 0) return false;
            
            if (node != "#") {
                diff += 2; // 非空节点有两个出度
            }
        }
        
        return diff == 0;
    }
}

var isValidSerialization = function(preorder) {
    const nodes = preorder.split(',');
    let slots = 1;
    
    for (let i = 0; i < nodes.length; i++) {
        slots--;
        if (slots < 0) return false;
        if (nodes[i] !== '#') slots += 2;
    }
    
    return slots === 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型度数统计法栈模拟法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

其中 n 为字符串长度。度数统计法是最优解法，只需要一次遍历且使用常数额外空间。