LeetCode LCP 10. 二叉树任务调度 — Java 实现题目概述任务以二叉树形式组织依赖关系根任务 root 需要等左右子树全部完成后才能执行。系统有 2 个 CPU 核任务可随时暂停/恢复。求完成所有任务的最小时间。---核心思路树形 DP对每个节点维护两个值值 含义sum 以该节点为根的子树中所有任务时间之和串行总时间min 以该节点为根的子树最小执行时间递推公式推导1. 总时间sum left.sum right.sum root.val2. 理想并行时间左右子树所有前置任务若能被 2 个 CPU 完美平分则需要 (left.sum right.sum) / 23. 实际限制但由于子树内部结构限制左右子树各自的最小执行时间 left.min、right.min 可能成为瓶颈4. 合并当前节点的最小时间为三者取最大再加上自身执行时间min root.val max(left.min, right.min, (left.sum right.sum) / 2.0)这个简洁公式在多个题解中被验证正确。---Java 代码java/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/class Solution {public double minimalExecTime(TreeNode root) {return dfs(root)[0];}/*** DFS 返回以 root 为根的子树的 [最小执行时间, 任务总时间]* return double[0] 最小执行时间, double[1] 所有节点值之和*/private double[] dfs(TreeNode root) {if (root null) {return new double[]{0.0, 0.0};}double[] left dfs(root.left);double[] right dfs(root.right);// 子树所有任务时间之和double sum left[1] right[1] root.val;// 最小执行时间 自身时间 max(左子树最小时间, 右子树最小时间, 左右总时间/2)double minTime root.val Math.max(Math.max(left[0], right[0]),(left[1] right[1]) / 2.0);return new double[]{minTime, sum};}}---示例验证示例 1root [47, 74, 31]47/ \74 31- 叶子节点[74] → (74, 74)[31] → (31, 31)- 根节点sum 74 31 47 152- min 47 max(74, 31, (7431)/252.5) 47 74 121 ✓示例 3root [1,3,2,null,null,4,4]1/ \3 2/ \4 4- 叶子 [4] → (4, 4)另一个 [4] → (4, 4)- 节点 2sum 442 10min 2 max(4, 4, 4) 6- 叶子 [3] → (3, 3)- 根节点 1sum 3101 14- min 1 max(3, 6, (310)/26.5) 1 6.5 7.5 ✓---复杂度分析项目 复杂度 说明时间 O(N) 每个节点访问一次空间 O(H) 递归栈深度H 为树高最坏 O(N)