题解 | #加分二叉树#

解读题意，题目给出了一种衡量二叉树的指标：加分，该指标依赖于各个结点的权值（分数）以及二叉树的树形。各结点的权值为已知条件，而树形为未知条件，因为同一中序遍历序列可以对应多个不同的二叉树，现在问：在这诸多可能的二叉树中，哪一棵树拥有最好的指标值，它的树形又是怎样的，要求给出其指标值和前序遍历序列。

解题思路：首先，既然存在多种不同的二叉树，我们自然想要去逐一确定树形并计算对应的指标，再从中挑出最好的那一棵。那么问题来了：对于给定的中序序列，应该如何确定可能的树形？我们发现，对于中序序列，我们可以选择序列中的任一结点作为父结点（设坐标为k），在其左边的序列，可以独立地作为左子树序列，右边的序列则可独立地作为右子树序列，那么自然而然地，我们会想到通过遍历来假设父结点，通过递归来假设子树。

优化思路，其实题目也已经明示了，这是一道动态规划题，而且递归方法也常常被动态规划法替代，问题在于：我们要规划什么？什么操作被重复地执行？显然，我们频繁地去计算子树的指标，对于同一棵树，某一子树只会被计算一次，但是我们现在面对着许多可能的树，某一子树会在多棵树中存在，所以我们接下来要做的是：在动态规划过程中表征这棵子树。具体来说，我们只需要通过左、右两个坐标(i,j)即可确定一段局部中序序列，这个序列对应的子树树形不是唯一的，但它的最佳子树指标值score是唯一的，而我们在动态规划中所需要的也只是这个最佳指标值罢了。所以，我们便得到了从(i,j)到score的映射，可以使用一个二维数组subScore来存储各个局部序列的最佳指标值。

数据的表示我们清楚了，那么该如何动态计算呢？前面我们通过遍历来假设父结点，其坐标设为k，那么根据指标的计算公式，有，不同的k坐标会得到不同的指标值，在遍历过程中我们只需从中选择最大值即可，即：

因为i<=j，我们实际上只使用了数组的上半部分，而题目要求我们输出树的前序序列，那么我们就需要存储各个子树根结点的坐标，这个坐标我们在取最大值的时候就确定了，就是最大值对应的k，我们可以将其存储在数组的下半部分：序列(i,j)对应的最佳子树根结点坐标放在subScore[j][i]位置。因为数组里存放了两种不同含义的值，按照规范我们应当将数组重命名为subScoreAndParents。最后可以利用递归进行前序遍历，输出前序序列，这个不是本题的核心考点，因此不再缀述，可以直接参考下方代码。

下附参考代码：

class Solution {
  public:
    // 为里使用一维数组来代替二维数组，因为二维数组要多次申请内存，而我很懒...
    int* subScoreAndParents = new int[960];

    // 递归实现的前序遍历算法，当子树结点不多于2个时，可以任选一个作为根结点
    void preTraverse(vector<int>& output, int start, int end) {
        if (end - start < 2) {
            output.push_back(start + 1);
            if (end - start == 1)
                output.push_back(start + 2);
        } else {
            int parentIdx = subScoreAndParents[(end << 5) + start];
            output.push_back(parentIdx + 1);
            if (start < parentIdx) preTraverse(output, start, parentIdx - 1);
            if (parentIdx < end) preTraverse(output, parentIdx + 1, end);
        }
    }

    vector<vector<int> > scoreTree(vector<int>& scores) {
        int n = scores.size();
        // 处理只有一个结点的序列
        for (int i = 0; i < n; i++)
            subScoreAndParents[(i << 5) + i] = scores[i];
        // 处理只有两个结点的序列
        for (int i = 1; i < n; i++)
            subScoreAndParents[((i - 1) << 5) + i] = scores[i-1] + scores[i];

        // 处理至少有3个结点的序列，其中，如果某一子树为空，我们将无法从数组中读取其指标值，需要特殊处理
        for (int i = n - 3, j, k; i > -1; i--) {
            for (j = i + 2; j < n; j++) {
                // 先计算左子树为空的情况
                int currScore = 0, maxScore = scores[i] + subScoreAndParents[((i + 1) << 5) + j], parentIdx = i;
                // 再计算左右子树非空的情况
                for (k = i + 1; k < j; k++) {
                    currScore = subScoreAndParents[(i << 5) + k - 1] * subScoreAndParents[((k + 1) << 5) + j] + scores[k];
                    if (currScore > maxScore) {
                        maxScore = currScore;
                        parentIdx = k;
                    }
                }
                // 后计算右子树为空的情况
                currScore = subScoreAndParents[(i << 5) + j - 1] + scores[j];
                if (currScore > maxScore) {
                    maxScore = currScore;
                    parentIdx = j;
                }
                // 保存结果
                subScoreAndParents[(i << 5) + j] = maxScore;
                subScoreAndParents[(j << 5) + i] = parentIdx;
            }
        }
        vector<vector<int>> result;
        vector<int> treeScore{subScoreAndParents[n - 1]};
        vector<int> preOrder;
        preTraverse(preOrder, 0, n - 1);
        result.push_back(treeScore);
        result.push_back(preOrder);

        return result;
    }
};