分析题目

1.给定的是一个二叉树的中序遍历，思考给定中序遍历有什么作用？ 二叉树的不同结构类型可以使1~n中的每一个数作为根节点，而且一旦确定了根节点，在整个序列中此点前面的序列构成左子树，右边的点构成右子树。

2.任意一颗二叉树分数的计算方法：（根为u)

• 既有左子树又有右子树 w[u] = w[u] + w[left(u)] + w[right(u)];
• 只有一个子树 w[u] = w[u] + w[left(u)] / w[right(u)];
• 叶子结点 w[u] = w[u];

3.要求输出前序遍历：先输出根，记录每个状态从哪转移而来？

状态表示

f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。

状态转移

枚举$k$, 代表根节点， [l, k - 1] 左子树, [k + 1, r] 右子树
f[i][j] = max(f[i][j], f[i][k - 1] * f[k + 1][j] + w[k])
同时我们记录每个区间（代表可能构成的树)的根节点 root[l][r] = k

最后前序遍历输出：

dfs(l, r); 每一个(l, r) 对应一个根$k$, 然后再分别递归左子树和右子树 dfs(l, k - 1), dfs(k + 1, r)

代码

#include <iostream>

using namespace std;

const int N = 30;

int n, w[N];
int f[N][N];
int root[N][N]; //f[i][j]  [i, j] 这段区间的根节点；

void dfs(int l, int r)
{
    if(l > r) return;
    int k = root[l][r];
    cout << k << ' ';
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> w[i];

    for(int len = 1; len <= n; len ++)
        for(int l = 1; l + len - 1 <= n; l ++)
        {
            int r = l + len - 1;

            for(int k = l; k <= r; k ++)
            {
                int left = k == l ? 1 : f[l][k - 1];
                int right = k == r ? 1 : f[k + 1][r];
                int score = left * right + w[k];
                if(l == r) score = w[k]; //特判
                if(f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;
                }
            }
        }
    cout << f[1][n] << endl;

    dfs(1, n);
}