题目链接
结论
现在我们拿到二叉树的一个节点
-
单独完成当前节点耗时
cur -
左子树所有任务时间和为
S1,最优并行后为T1 -
右子树所有任务时间和为
S2,最优并行后为T2
那么限制左、右子树的任务执行总时间的因素只有两个：
-
两侧时间和的平均值 \(\frac{S1 + S2}{2}\)
-
两侧最优时间的最大值
max(T1, T2)
则完成当前节点所需的最短总时间 T= max( \(\frac{S1 + S2}{2}\) , max( T1, T2) ) + cur
当前结点的状态为 { S1 + S2 + cur , T }
二叉树自底向上更新状态
class Solution {
public:double minimalExecTime(TreeNode* root) {return dfs(root).second;}pair<double,double>dfs(TreeNode*root){if(root==NULL)return {0,0};auto [lsum,t1]=dfs(root->left);auto [rsum,t2]=dfs(root->right);int sum=lsum+rsum+root->val;return {sum,root->val+max((lsum+rsum)/2.0,max(t1,t2))};}
};
证明请看这位大佬的帖子