NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 26 题

#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep)
{
    ans = ans + dep*(s1[x] - 'A' + 1);
    if (lefts[x] >= 0) calc(lefts[x], dep+1);
    if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x)
{
    if (lefts[x] >= 0) check(lefts[x]);
    s3 = s3 + s1[x];
    if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th)
{
    if (th == n)
    {
        s3 = "";
        check(0);
        if (s3 == s2)
        {
            ans = 0;
            calc(0, 1);
            cout<<ans<<endl;
        }
        return;
    }
    if (lefts[x] == -1 && rights[x] == -1)
    {
        lefts[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        lefts[x] = -1;
    }
    if (rights[x] == -1)
    {
        rights[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        rights[x] = -1;
    }
    if (father[x] >= 0)
        dfs(father[x], th);
}
int main()
{
    cin>>s1;
    cin>>s2;
    n = s1.size();
    memset(lefts, -1, sizeof(lefts));
    memset(rights, -1, sizeof(rights));
    memset(father, -1, sizeof(father));
    dfs(0, 1);
}

输入： ABCDEF BCAEDF 输出：__________

这道题考的是二叉树的先序构造与中序验证，以及树形结构上的深度加权求和。拿到题先别急着跑代码，盯着 dfs 里那三个 if 分支：它是在用 s1 当先序序列硬凑一棵树，每凑一个节点就递归搜左右子树，凑不成就回退。核心就是看 s1 能否按先序拼出一棵二叉树，拼好后跑一遍 check 把中序跑出来跟 s2 比，比得上才累加答案。

最容易掉进两个坑：一是把 dfs 当成普通先序遍历，以为只要 s1 能按先序填满就一定是二叉搜索树，其实题目只要求任意二叉树，关键是父节点指针 father 的赋值时机和回溯要跟上，否则树结构就串了；二是算 ans 时把深度搞错，dep 是从根开始算的，根是 1，每下一层 +1，别把 dep 当成节点编号或者从 0 开始，那样算出来的数肯定偏小；三是 check 里 s3 是全局变量，每次 dfs 分支里 s3 累加后必须清空，否则后面匹配会串，代码里 s3="" 那行就是防这个，很多人会忽略清空导致假匹配。

程序阅读——二叉树构造与权值计算

输入 s1=ABCDEF, s2=BCAEDF

程序尝试构建二叉树使得先序=s1，检查中序是否=s2。 当找到匹配时，计算∑(dep×(s1[x]-'A'+1))。

追踪可得到树结构和深度，最终 ans=55。

核心逻辑拆解

1. dfs 的工作流：先序构造 + 回溯

dfs 的参数是 (当前节点 x, 下一个要填的节点序号 th)。

• 当 th==n 时，说明整条路径已经填满了 n 个节点，此时调用 check(0) 把整棵树的中序跑出来，跟 s2 比。如果相等，就把 ans 清零，再调用 calc(0,1) 从根开始算深度加权值，然后输出 ans。
• 如果当前节点 x 的左右孩子都还没填（lefts[x]==-1 && rights[x]==-1），说明 x 是叶子，不能再往下挂，直接回溯。
• 如果只有右孩子没填（rights[x]==-1），就把 th 挂到 rights[x]，设置 father[th]=x，递归 dfs(th, th+1)，递归回来后再把 father[th] 和 rights[x] 恢复成 -1，这是典型的回溯。
• 如果只有左孩子没填，同理处理。
• 最后如果 x 有父亲（father[x]>=0），说明 x 是某个节点的子节点，递归往上走 dfs(father[x], th)，继续尝试用剩下的节点去补父亲的其他子节点。

整个 dfs 就是在用 s1 当先序序列，一层一层去“硬凑”一棵二叉树，凑不成就回退，凑成且中序匹配就停。