golang 解法, 执行用时: 16 ms, 内存消耗: 7 MB, 提交时间: 2023-06-13 10:48:48

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minimalExecTime(root *TreeNode) float64 {
    var dfs func(node *TreeNode)(max, par float64)
    dfs = func(node *TreeNode)(max, par float64) {
        if node == nil {
            return 0.0, 0.0
        }
        max = float64(node.Val)
        a, b := dfs(node.Left)
        c, d := dfs(node.Right)
        max += a + c
        if a < c {
            a, c = c, a
            b, d = d, b
        }
        if a - c <= 2 * b {
            par = (a + c) / 2
        } else {
            par = b + c
        }
        return max, par
    }
    max, par := dfs(root)
    return max - par
}

cpp 解法, 执行用时: 40 ms, 内存消耗: 41.7 MB, 提交时间: 2023-06-13 10:48:28

/**
 * 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<int, double> DFS(TreeNode* root) {
        if (!root) return {0, 0.0};
        auto l = DFS(root->left);
        auto r = DFS(root->right);

        return {l.first + r.first + root->val, root->val + max(max(l.second, r.second), (l.first + r.first) / 2.0)};
    }
    double minimalExecTime(TreeNode* root) {
        auto p = DFS(root);
        return p.second;
    }
};

cpp 解法, 执行用时: 52 ms, 内存消耗: 41.8 MB, 提交时间: 2023-06-13 10:47:23

/**
 * 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<int, double> DFS(TreeNode* root) {
        if (!root) return {0, 0.0};
        auto l = DFS(root->left);
        auto r = DFS(root->right);

        int a = l.first, c = r.first;
        double b = l.second, d = r.second;
        int tot = a + c + root->val;
        if ((c - 2 * d <= a && a <= c) || (a - 2 * b <= c && c <= a)) {
            return {tot, (a + c) / 2.0};
        }
        if (a - 2 * b > c) {
            return {tot, b + c};
        } else {
            // c - 2 * d > a
            return {tot, a + d};
        }
    }
    double minimalExecTime(TreeNode* root) {
        auto p = DFS(root);
        return p.first - p.second;
    }
};

python3 解法, 执行用时: 84 ms, 内存消耗: 17.1 MB, 提交时间: 2023-06-13 10:46:53

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minimalExecTime(self, root: TreeNode) -> float:
        def dfs(root: TreeNode) -> (int, int):
            if root is None:
                return 0., 0.
            tc = root.val
			
            # 先递归左右子树
            a, b = dfs(root.left)
            c, d = dfs(root.right)
            
            tc = tc + a + c
            # 只考虑 a >= c 的情况，不满足就交换
            if a < c:
                a, c = c, a
                b, d = d, b
            
            if a - 2 * b <= c:
                pc = (a + c) / 2
            else:
                pc = c + b

            return tc, pc

        tc, pc = dfs(root)
        return tc - pc

java 解法, 执行用时: 2 ms, 内存消耗: 42.6 MB, 提交时间: 2023-06-13 10:45:30

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * LCP 10. 二叉树任务调度
     * @param root
     * @return
     */
    public double minimalExecTime(TreeNode root) {
        double[] res = execTime(root,2);
        return res[0];
    }

    /**
     * 获取node最小执行时间
     * @param node node
     * @param n 并行数
     * @return [0]执行完当前节点最小耗时，[1]当前node为根的时间串行之和
     */
    private double[] execTime(TreeNode node,int n){
        if (node == null){
            // [0]执行完当前节点最小耗时，[1]当前node为根的时间串行之和
            return new double[]{0.0D,0.0D};
        }
        // 获取左右子树的值
        double[] leftTime = execTime(node.left,n);
        double[] rightTime = execTime(node.right,n);
        // 左右子树节点之和
        double sum = leftTime[1] + rightTime[1];
        // 当前节点执行完的最小消耗时间
        double minTime = Math.max(Math.max(leftTime[0],rightTime[0]),sum/n) + node.val;
        return new double[]{minTime,sum + node.val};
    }
}

python3 解法, 执行用时: 120 ms, 内存消耗: 17.3 MB, 提交时间: 2023-06-13 10:44:58

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# 树形dp
class Solution:
    def minimalExecTime(self, root: TreeNode) -> float:
        def dfs(rt):
            if not rt: return 0,0
            l = dfs(rt.left)
            r = dfs(rt.right)
            return max(l[0], r[0], (l[1]+r[1])/2)+rt.val, l[1]+r[1]+rt.val
        return dfs(root)[0]