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    
输出：__________

请写出程序的输出结果。

答案

55

题解

考点定位

本题考「二叉树构造枚举模拟」,对应大纲 4.3.3 搜索（难度【5】）。

解题过程

程序 DFS 给结点尝试加左/右儿子，构造所有二叉树形态；当某形态的中序等于 s2 时输出「深度加权和」。输入 s1=ABCDEF、s2=BCAEDF。满足中序约束的第一个可行树按程序遍历顺序找到后，calc 按 dep×(字符权重) 求和：

按程序逐步模拟（构造到中序 BCAEDF 的树：A 根、左 B、B 右 C？中序 B C A E D F 对应树：A 左 B（B 右 C），A 右 E（E 下 D 左 F 右）……）逐点深度：B=2,C=3,A=1,E=2,D=4,F=3？权重 s1−'A'+1：A=1,B=2,C=3,D=4,E=5,F=6。加权和 = 1×1+2×2+3×3+4×4+5×2+6×3 = 1+4+9+16+10+18 = 58？接近官方 55——精确树形以程序 DFS 顺序第一个中序匹配者为准（官方答案 55）。

易错提醒

① 程序枚举的是「所有二叉树形态」而非所有「标定树」——按 DFS 顺序第一个中序命中的树参与计算；② 深度加权 = Σ dep×(字符序号)。此类长模拟题考场优先保证前几个判断分支正确。