Kimi LeetCode LCP 10. 二叉树任务调度 Rust实现

以下是 LCP 10. 二叉树任务调度 的 Rust 实现。核心思路这道题是经典的树形 DP。对每个节点维护两个值值 含义sum 该子树所有任务的总时间单核串行执行需要的时间parallel 该子树中最大可以并行的时间最终答案 sum - parallel总时间减去能并行的时间合并左右子树的关键推导设左子树 (suma, parallelb)右子树 (sumc, paralleld)且 a c- 情况 1a - 2*b c左子树中只能串行的部分可以被右子树完全覆盖左右可以完全并行 → parallel (a c) / 2- 情况 2a - 2*b c左子树有一部分任务无论如何只能串行 → parallel c bRust 代码rust// Definition for a binary tree node.#[derive(Debug, PartialEq, Eq)]pub struct TreeNode {pub val: i32,pub left: OptionRcRefCellTreeNode,pub right: OptionRcRefCellTreeNode,}impl TreeNode {#[inline]pub fn new(val: i32) - Self {TreeNode {val,left: None,right: None,}}}use std::rc::Rc;use std::cell::RefCell;struct Solution;impl Solution {/// LCP 10. 二叉树任务调度////// 对每个节点DFS 返回 (子树总时间, 子树最大并行时间)/// 最终答案 总时间 - 最大并行时间pub fn minimal_exec_time(root: OptionRcRefCellTreeNode) - f64 {let (sum, parallel) Self::dfs(root);sum - parallel}fn dfs(root: OptionRcRefCellTreeNode) - (f64, f64) {match root {None (0.0, 0.0),Some(node) {let node node.borrow();let (left_sum, left_parallel) Self::dfs(node.left.clone());let (right_sum, right_parallel) Self::dfs(node.right.clone());// 确保 a c方便后续讨论let (a, b, c, d) if left_sum right_sum {(left_sum, left_parallel, right_sum, right_parallel)} else {(right_sum, right_parallel, left_sum, left_parallel)};let total a c node.val as f64;let parallel if a - 2.0 * b c {// 可以完全并行(a c) / 2.0} else {// 左子树有部分只能串行c b};(total, parallel)}}}}验证示例输入 输出 说明[47, 74, 31] 121.0 左右叶子并行 31剩余 4347 串行[15, 21, null, 24, null, 27, 26] 87.0 链式结构最优并行时间 26[1, 3, 2, null, null, 4, 4] 7.5 利用子树内部并行时间互相拆借复杂度- 时间复杂度O(n)每个节点只访问一次- 空间复杂度O(h)递归栈深度h 为树高