数据结构与算法之二叉树: LeetCode LCP 10. 二叉树任务调度 (Ts版)

二叉树任务调度

• https://leetcode.cn/problems/er-cha-shu-ren-wu-diao-du/description/

描述

• 任务调度优化是计算机性能优化的关键任务之一。在任务众多时，不同的调度策略可能会得到不同的总体执行时间，因此寻求一个最优的调度方案是非常有必要的

• 通常任务之间是存在依赖关系的，即对于某个任务，你需要先完成他的前导任务（如果非空），才能开始执行该任务。我们保证任务的依赖关系是一棵二叉树，其中 root 为根任务，root.left 和 root.right 为他的两个前导任务（可能为空），root.val 为其自身的执行时间

• 在一个 CPU 核执行某个任务时，我们可以在任何时刻暂停当前任务的执行，并保留当前执行进度。在下次继续执行该任务时，会从之前停留的进度开始继续执行。暂停的时间可以不是整数

• 现在，系统有两个 CPU 核，即我们可以同时执行两个任务，但是同一个任务不能同时在两个核上执行。给定这颗任务树，请求出所有任务执行完毕的最小时间

示例 1

输入：root = [47, 74, 31]
输出：121

解释：根节点的左右节点可以并行执行31分钟，剩下的43+47分钟只能串行执行，因此总体执行时间是121分钟

示例 2

输入：root = [15, 21, null, 24, null, 27, 26]
输出：87

示例 3

输入：root = [1,3,2,null,null,4,4]
输出：7.5

限制

• 1 <= 节点数量 <= 1000
• 1 <= 单节点执行时间 <= 1000

Typescript 版算法实现

1 ) 方案：深度优先

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}

function dfs(root: TreeNode | null): [number, number] {
  if (!root) return [0, 0.0];
  
  const [leftSum, leftAvg] = dfs(root.left);
  const [rightSum, rightAvg] = dfs(root.right);

  const a = leftSum, c = rightSum;
  const b = leftAvg, d = rightAvg;
  const 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];
  }
}

function minimalExecTime(root: TreeNode | null): number {
  const [totalSum, averageTime] = dfs(root);
  return totalSum - averageTime;
}

2 ) 方案2：深度优先-优化

// 定义二叉树节点结构
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}

function dfs(root: TreeNode | null): [number, number] {
  if (!root) return [0, 0.0];

  const [leftSum, leftMaxExecTime] = dfs(root.left);
  const [rightSum, rightMaxExecTime] = dfs(root.right);

  const totalSum = leftSum + rightSum + root.val;
  const maxExecTime = root.val + Math.max(
      Math.max(leftMaxExecTime, rightMaxExecTime),
      (leftSum + rightSum) / 2.0
  );

  return [totalSum, maxExecTime];
}

function minimalExecTime(root: TreeNode | null): number {
  const [, maxExecTime] = dfs(root);
  return maxExecTime;
}