这道题的关键在于为每个子树维护两个值并通过树形DP计算最优调度方案。核心解法有两种思路这里先展示更为简洁、易于理解的一种再补充完整的推导过程。核心思路树形DP对于以node为根的子树维护两个值· total: 子树所有任务的总执行时间串行总和。· maxExec: 在最优调度下该子树从开始执行到全部完成所需的最短时间。对于任意节点其最优时间 maxExec 是以下三者的最大值1. 左子树的最优时间。2. 右子树的最优时间。3. 两个CPU完全并行执行左右子树总时间的一半即 (left.total right.total) / 2。加上当前节点自身的执行时间root-val后maxExec即为所求。C代码实现cpp/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {public:// 返回 pair: {子树总执行时间, 子树最优调度完成时间}pairdouble, double dfs(TreeNode* root) {if (root nullptr) {return {0.0, 0.0};}auto left dfs(root-left);auto right dfs(root-right);double total root-val left.first right.first;// 核心递推公式取左、右子树最优时间和并行执行两子树总时间三者的最大值[citation:7][citation:11]double maxExec root-val max({left.second,right.second,(left.first right.first) / 2.0});return {total, maxExec};}double minimalExecTime(TreeNode* root) {return dfs(root).second;}};关键说明· max函数使用C11的std::initializer_list版本max({a, b, c})需要algorithm头文件LeetCode环境通常已包含。· 数据类型结果为浮点数使用double。更详细的推导思路另一种常见解法是维护“总时间”和“不可避免的串行时间”。核心逻辑是最优策略是先尽可能让两个CPU并行最后剩余无法并行的部分只能串行。· 假设a和b是两棵子树的信息first总时间second必须串行的时间。· 最终答案为 (a.first b.first) / 2 (剩余串行时间) / 2。剩余串行时间根据子树情况分三种1. 左子树串行时间 右子树总时间剩余串行时间为 左.second - 右.first。2. 右子树串行时间 左子树总时间剩余串行时间为 右.second - 左.first。3. 其他情况左右子树的任务可以被完全并行消化剩余串行时间为 0。
DeepSeek LeetCode LCP 10. 二叉树任务调度 C++实现
这道题的关键在于为每个子树维护两个值并通过树形DP计算最优调度方案。核心解法有两种思路这里先展示更为简洁、易于理解的一种再补充完整的推导过程。核心思路树形DP对于以node为根的子树维护两个值· total: 子树所有任务的总执行时间串行总和。· maxExec: 在最优调度下该子树从开始执行到全部完成所需的最短时间。对于任意节点其最优时间 maxExec 是以下三者的最大值1. 左子树的最优时间。2. 右子树的最优时间。3. 两个CPU完全并行执行左右子树总时间的一半即 (left.total right.total) / 2。加上当前节点自身的执行时间root-val后maxExec即为所求。C代码实现cpp/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {public:// 返回 pair: {子树总执行时间, 子树最优调度完成时间}pairdouble, double dfs(TreeNode* root) {if (root nullptr) {return {0.0, 0.0};}auto left dfs(root-left);auto right dfs(root-right);double total root-val left.first right.first;// 核心递推公式取左、右子树最优时间和并行执行两子树总时间三者的最大值[citation:7][citation:11]double maxExec root-val max({left.second,right.second,(left.first right.first) / 2.0});return {total, maxExec};}double minimalExecTime(TreeNode* root) {return dfs(root).second;}};关键说明· max函数使用C11的std::initializer_list版本max({a, b, c})需要algorithm头文件LeetCode环境通常已包含。· 数据类型结果为浮点数使用double。更详细的推导思路另一种常见解法是维护“总时间”和“不可避免的串行时间”。核心逻辑是最优策略是先尽可能让两个CPU并行最后剩余无法并行的部分只能串行。· 假设a和b是两棵子树的信息first总时间second必须串行的时间。· 最终答案为 (a.first b.first) / 2 (剩余串行时间) / 2。剩余串行时间根据子树情况分三种1. 左子树串行时间 右子树总时间剩余串行时间为 左.second - 右.first。2. 右子树串行时间 左子树总时间剩余串行时间为 右.second - 左.first。3. 其他情况左右子树的任务可以被完全并行消化剩余串行时间为 0。
)
)
