algorithm - 通过在每一步递增相邻节点来找到使所有树节点为零所需的最小值

Question

1. 问题是找到使所有节点都为零所需的最小值，我们称之为 K。

2. 给出了一个非二叉树。

3. 在第一步中，您可以选择一个节点作为起点。如果 K 大于该节点的值，则将该值更改为零，并增加距离为一或两个的其他节点的值。请注意，一旦节点的值变为零，它就不会再递增，也不会允许与其相连的节点递增。

4. 然后选择距离为1且至少有一个零值节点的另一个节点，重复该过程

示例:

5
 \
  2 
   \
    5

当我们从值为 5 的叶子开始时，我们有

6
 \
  3
   \
    0

那么我们应该选择3；我们不能选择 6，因为它在距离 1 中没有零节点!

7
 \
  0
   \
    0

最后我们选择 7 并且 K = 7 但如果我们一开始选择 2 那么我们有:

6
 \
  0
   \
    6

那么我们应该选择6；因为值为 2 的节点现在为零，所以连接被切断，并且通过更改值为 6 的节点的值，不会再发生增量!

0
 \
  0
   \
    6

所以最小 K = 6

我目前的做法:

1. 找到最大节点并从它开始(如果有多个最大节点，则选择较早出现的节点)

2. 我定义了一个数组，我们称之为可能的节点，并将在第 1 步中找到的节点添加到它。

3. 虽然 possible nodes 不为空，但我执行以下步骤:

   一个。选择可能节点中的最大值；我们称它为max_node

   使 max_node 幂为零并更新 K

   增加其 parent 、祖 parent 、子女、孙子女和 sibling 的值(value)(如果他们之前不为零)

   将具有非零值的父节点和子节点添加到可能的节点

   从可能的节点

中移除 max_node

其实这是一道作业题，但这种做法不对!它会给出错误的答案并达到超时限制。

约束

• 节点数≤3×10⁵

• -10⁹ ≤ 节点值≤ 10⁹

• 时间限制:2.5 秒

• 内存限制:256 MB

Answer 1

如果你从树中的一个随机节点开始，那么 K 是以下项中的最大值:

1. 起始节点
2. 它的 child + 1
3. 它的 parent + 1
4. 所有其他节点 + 2

这是因为你只能选择与它相邻的 0 节点的节点并且这些节点不会递增。

我们可以得出结论，Kmin 必须介于 max 和 max + 2 之间。

所以 O(n) 算法可能如下所示:

1. 找到最大节点值 max 并计算有多少节点具有该值 => maxCount
2. 如果 maxCount = 1 然后计算有多少节点具有值 max - 1 => max1Count，有两种可能性:
   1. max1Count = 0 或值为 max - 1 的节点与值为 max 的节点的相邻节点数等于 max1Count => 解是max
   2. 否则解是max + 1
3. 找到树中最高的具有max 值的所有节点:
   1. 如果第一次出现 max 的深度只有一个节点:
      1. 值为 max 的 child 的数量等于 maxCount - 1 => 解决方案是 max + 1
      2. 只有一个值为 max 的 child ，其值为 max 的 child 的数量等于 maxCount - 2 =>解决方案也是 max + 1
      3. 没有值为 max 的 child ，但有 maxCount - 1 个孙子，它们都具有相同的父级和值 max =>解决方案也是 max + 1
      4. 否则解是max + 2
   2. 如果您找到 maxCount 个节点并且它们都有相同的父节点 => 解决方案是 max + 1
   3. 否则解是max + 2