验证二叉树的前序序列化 图解题解

一串记号，怎么判断它是不是合法的前序序列化

给一串逗号分隔的记号，数字是真实节点、# 是空节点，判断它是不是某棵二叉树的合法前序序列化——即按「先根、再左子树、再右子树」记、空孩子也补个 # 的那串；且不许真把树建出来。题面 preorder="9,3,4,#,#,1,#,#,2,#,6,#,#" 返回 true，"1,#"、"9,#,#,1" 返回 false。

光数 # 的个数，为什么判不出来

一棵有 m 个真实节点的二叉树恰好带 m+1 个空位，数 # 够不够不就行？可数量对不代表拼得成树。"1,#" 里真节点 1 只跟着一个 #，少了一个孩子、搭不起完整的树。合不合法卡在记号的先后次序，不在个数多少。

一棵完成的子树，和一个 # 没有区别

一个真实节点，只要左右孩子都到齐，以它为根的子树就整体看成一个空位——一棵搭完的子树，在父节点眼里和一个 # 没区别。于是不必知道整棵树的样子，只要反复把「一个真值后面紧跟两个 #」这种最小完整子树折成一个 #，看整串最后能不能折成单个 # 就行。这需要一个栈，也就是后进先出的一叠记号。

压栈、折叠，栈里最后该剩什么

把整串按逗号切成记号逐个压栈。每压一个查栈顶：最上面两个都是 #、下面第三个是真值（不是 #），就说明这个真值配齐了两个空孩子，把这三个弹掉、压回一个 #。折完可能又让新栈顶凑成「真值，#，#」，就接着折，直到栈顶不再是这形状。记号读完栈里恰好剩一个 # 就合法。第三个必须是真值不能省：只盯栈顶两个 # 就折，"#,#,#" 这种没有父节点的空孩子也会被错折进去。

拿题面这串记号从头折到尾

用题面的 9,3,4,#,#,1,#,#,2,#,6,#,# 走一遍。9、3、4 压栈成 9,3,4；两个 # 进来成 9,3,4,#,#，栈顶两 # 底下是真值 4，配齐两孩子折成 #，栈变 9,3,#。再压 1、#、#，栈到 9,3,#,1,#,#：先折 1,#,# 成 #（栈成 9,3,#,#），又让 3,#,# 露头接着折成 #，栈只剩 9,#。

接着 2,#,6,#,# 进来成 9,#,2,#,6,#,#：6,#,# 折成 #，紧跟 2,#,# 折成 #，最后 9,#,# 也折成一个 #。十三个记号读尽，栈里正好剩一个 #，返回 true，这串是合法序列化。

线性一趟，哪些串一压就露馅

每个记号压栈一次，折叠次数也不超过记号数，整趟线性 O(n)。空间花在栈上，最坏栈里压着近 n 个记号，是 O(n)。有个实现坑：参考代码用 Python 切片 stk[:-3] 重建前缀，最坏退化到 n 的平方；换成 del stk[-3:] 原地删末尾三个就稳在 O(n)，C++、Java 原地弹栈天然 O(n)。

两种串一压就露馅。"1,#" 是树没搭完就到头：真节点 1 只等来一个 #，栈里留着 1,# 折不动，读完剩两个记号而非单个 #，false。"9,#,#,1" 反过来是树搭完了还拖尾巴：9,#,# 先折成一个 #，本该到此结束，后面偏冒出个 1，栈成 #,1，再折不回单个 #，同样 false。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        stk = []
        for c in preorder.split(","):
            stk.append(c)
            while len(stk) > 2 and stk[-1] == stk[-2] == "#" and stk[-3] != "#":
                stk = stk[:-3]
                stk.append("#")
        return len(stk) == 1 and stk[0] == "#"

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    bool isValidSerialization(string preorder) {
        vector<string> stk;
        stringstream ss(preorder);
        string s;
        while (getline(ss, s, ',')) {
            stk.push_back(s);
            while (stk.size() >= 3 && stk[stk.size() - 1] == "#" && stk[stk.size() - 2] == "#" && stk[stk.size() - 3] != "#") {
                stk.pop_back();
                stk.pop_back();
                stk.pop_back();
                stk.push_back("#");
            }
        }
        return stk.size() == 1 && stk[0] == "#";
    }
};

Java

import java.util.*;
class Solution {
    public boolean isValidSerialization(String preorder) {
        List<String> stk = new ArrayList<>();
        for (String s : preorder.split(",")) {
            stk.add(s);
            while (stk.size() >= 3 && stk.get(stk.size() - 1).equals("#")
                && stk.get(stk.size() - 2).equals("#") && !stk.get(stk.size() - 3).equals("#")) {
                stk.remove(stk.size() - 1);
                stk.remove(stk.size() - 1);
                stk.remove(stk.size() - 1);
                stk.add("#");
            }
        }
        return stk.size() == 1 && stk.get(0).equals("#");
    }
}