P4874 二叉树结点的子孙数（基础）

解题思路

第一步，看懂"扩展后序序列"。 扩展二叉树把空子树补成"."，后序遍历先输出左子树序列、再右子树序列、最后输出根。所以整个序列的最后一位一定是整棵树的根，往前是右子树和左子树的部分。

第二步，倒着读建树。 用下标 idx 从字符串末尾往前读。函数 build() 读一个字符 c：如果是 . 返回 0；否则新建结点，先递归建右子树，再递归建左子树。因为后序是"左、右、根"，倒过来读就是"根、右、左"，所以要反过来建。

第三步，理解"子孙"的含义。 一个结点的子孙包括它的所有孩子、孩子的孩子……也就是整棵以它为根的子树，但不包括它自己。比如一个结点只有一个孩子，且这孩子没有孩子，那么它的子孙数就是 1。

第四步，递归统计。 函数 cnt(u) 这样算：如果 u 有左孩子，答案加上 1 再递归统计左孩子的子孙；如果 u 有右孩子，同样加 1 再递归。把两边加起来就是 u 的子孙数。

第五步，找到查询结点。 第二行给一个小写字母，字母不会重复。扫描建好的树，找到字母相同的结点，调用 cnt 输出答案。

举个例子。 样例序列 ..b..d.ca，最后一位是 a，倒着读建出：a 的右孩子是 c，c 的左孩子是 d，a 的左孩子是 b。查询 c：c 只有一个孩子 d，d 没有孩子，所以答案是 1，与样例一致。

边界情况。 如果查询的是叶子结点，没有孩子，答案就是 0。序列长度最大 255，数组开到 260 足够。

参考代码

// 扩展后序求子孙数：倒序读入建树，再递归统计子孙个数
#include <iostream>
using namespace std;

char s[260];
int n;         // 字符串长度
int idx;       // 从后往前读的下标

struct Node {
    char v;
    int lef, rig;
} t[260];
int tot;

// 倒序建树：后序最后一个是根，先建右子树再建左子树
int build() {
    char c = s[idx--];
    if (c == '.') return 0;
    int u = ++tot;
    t[u].v = c;
    t[u].rig = build();   // 右子树
    t[u].lef = build();   // 左子树
    return u;
}

// 统计 u 的子孙个数（不含自己）
int cnt(int u) {
    int res = 0;
    if (t[u].lef) res += 1 + cnt(t[u].lef);
    if (t[u].rig) res += 1 + cnt(t[u].rig);
    return res;
}

int main() {
    cin >> s;
    n = 0;
    while (s[n]) n++;     // 求长度
    idx = n - 1;
    build();              // 建整棵树
    char q;
    cin >> q;             // 要查询的结点
    for (int i = 1; i <= tot; i++)
        if (t[i].v == q) {
            cout << cnt(i) << endl;
            break;
        }
    return 0;
}

复杂度分析

时间复杂度。 建树时每个字符读一次，O(n)；统计子孙时以查询结点为根的子树每个结点访问一次，最坏是整个树，O(n)。总时间复杂度 O(n)，n 最大 255，非常快。

空间复杂度。 字符数组和结点数组都是 O(n)，递归深度最坏 O(n)，总空间复杂度 O(n)。