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

这道题到底在问什么

输入

"9,3,4,#,#,1,#,#,2,#,6,#,#"

输出

true

输入

"1,#"

输出

false

输入

"9,#,#,1"

输出

false

先想最直接的笨办法

先把序列按逗号切成 13 个记号，挨个读。我们不重建树，只维护一个栈：每读一个记号压栈，栈顶一旦凑出「真值, #, #」就把这三个压成一个 #。读完后栈里恰好只剩一个 #，就合法。（动画第 4 步）

最优解：一步一步想明白

1. 3记住这一句：真节点配齐两个 # 就坍缩成一个 #。下面每一帧都在套它。
2. 4先把序列按逗号切成 13 个记号，挨个读。我们不重建树，只维护一个栈：每读一个记号压栈，栈顶一旦凑出「真值, #, #」就把这三个压成一个 #。读完后栈里恰好只剩一个 #，就合法。
3. 5读入第 0 个 “9”，它是真实节点，直接压入栈顶。栈顶还没凑出「真值, #, #」的形状，不坍缩，继续往后读。
4. 6读入第 1 个 “3”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。
5. 7读入第 2 个 “4”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。
6. 8读入第 3 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。
7. 9读入第 4 个 “#”(空节点)压栈，这下栈顶正好是「真值, #, #」，可以坍缩了。
8. 10“4” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 4, #, # 压成一个 #。坍缩后栈顶不再是可坍缩形状，暂停，接着读下一个记号。
9. 11读入第 5 个 “1”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。
10. 12读入第 6 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。
11. 13读入第 7 个 “#”(空节点)压栈，这下栈顶正好是「真值, #, #」，可以坍缩了。
12. 14“1” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 1, #, # 压成一个 #。坍缩后栈顶又凑出「真值, #, #」，继续往下坍。
13. 15“3” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 3, #, # 压成一个 #。坍缩后栈顶不再是可坍缩形状，暂停，接着读下一个记号。
14. 16读入第 8 个 “2”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。
15. 17读入第 9 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。
16. 18读入第 10 个 “6”，真实节点压入栈顶。栈顶暂时还不构成可坍缩的形状，接着读下一个。
17. 19读入第 11 个 “#”(空节点)压栈。栈顶只有一个 #，还差一个，先不坍缩，继续读。
18. 20读入第 12 个 “#”(空节点)压栈，这下栈顶正好是「真值, #, #」，可以坍缩了。
19. 21“6” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 6, #, # 压成一个 #。坍缩后栈顶又凑出「真值, #, #」，继续往下坍。
20. 22“2” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 2, #, # 压成一个 #。坍缩后栈顶又凑出「真值, #, #」，继续往下坍。
21. 23“9” 的左右孩子都到齐了，以它为根的小子树整体退化成一个空位，把栈顶三个 9, #, # 压成一个 #。坍缩后栈只剩一个 #，进入终局判定。
22. 2413 个记号全部读完，栈里恰好只剩一个 “#”。这说明整串正好拼成一棵完整二叉树的前序序列化，合法，返回 true，正是示例 1 的答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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] == "#"

#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] == "#";
    }
};

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("#");
    }
}

复杂度

面试官可能追问