将二叉搜索树中的所有大于值的节点加上

二叉搜索树（BST）是一种二叉树，它满足所有左叶子节点的值必须小于根节点，而所有右叶子节点的值必须大于根节点的性质。在这个分组的意义上，创建一个二叉树来增加BST中节点的价值，方法是将其加上所有更大的值。简化过程可以这样实现：对于给定的BST，将所有大于当前节点值的节点值加到该节点值上。

问题陈述

对于二叉搜索树（BST）的指定子树，只需将当前节点左子树中所有大于当前节点的值相加即可。

方法 - 1

实现此操作最可行的方法是反转给定二叉搜索树（BST）的中序遍历。在中序反向遍历中，我们按从大到小的顺序查看节点。在遍历过程中，我们跟踪已访问的所有值的总和，这会得到所有更大值的总和。

算法步骤

1. 初始化一个全局变量 sum，其值为 0。
2. 对 BST 执行反向中序遍历。
3. 在每个节点上，执行以下步骤：
4. 递归访问右子树。
   • 将当前节点的值添加到 aggregate（sum）中。
   • 将当前节点的值更新为 aggregate。
   • 递归访问左子树。

Java 代码实现

输出

说明

1. 初始化

• 我们从一个名为 sum 的全局变量开始，其初始值为 0。该变量将用于在遍历过程中跟踪每个节点遇到的更大值的总和。

2. 反向中序遍历

• 我们在此完成反向中序树遍历，从而以升序访问节点值。
• 在反向重复中序遍历的过程中，我们首先获取右子树的节点值，然后是子树的当前节点，最后到达左子树的节点值。

3. 访问每个节点

• 在遍历过程中的每个节点上，我们执行以下步骤：
• 递归访问右子树：通过这种机制，我们确保节点访问的顺序是从值较大的节点到当前节点。
• 将当前节点的值加到 sum 中：在那边向相反方向移动时，不断增长的节点值将逐渐覆盖我们迄今为止已经征服的所有有偏值。因此，我们不仅在 sum 上前进，还在链表中后退。
• 更新当前节点的值：我们将 'sum' 的当前值赋给当前节点，它结合了迄今为止所有乘数的前值。这暗示了二叉搜索树的基本原理，它通过选择当前所有值中最大的值来完善其辅助能力。
• 递归访问左子树：最终，我们递归地遍历左子树以继续该过程的迭代。

4. 示例

• 考虑以下 BST：根节点值为 (5)，左子节点值为 (2)，右子节点值为 (13)。
• 随后，沿着在最后阶段使用的右子树，我们执行反向中序遍历。因此，节点 (13) 将首先被访问，其值被加到 sum 中，sum 被替换为其值，然后访问左子树。
• 第三，我们处理根节点，值为 5，此时 sum 为 18。然后我们将值更新为 sum（sum 现在为 18），并移动到我们的左子树。
• 接下来，我们转到左子节点，其值为 2，将值推送到 sum（20），并将其值更新为 20。
• 在这种情况下，我们遍历 BST 并将所有大于该节点的节点值之和赋予每个节点。

5. 时间复杂度

• 算法的复杂度为 O(N)，其中 N 是 BST 中的节点数。因为给定节点在沿着所有路径时只被访问一次。

6. 空间复杂度

• 算法的空间复杂度为 O(H)，其中 H 是 BST 的高度。在这种情况下，调用堆栈上的步骤是遍历期间递归算法调用的结果。

通过此算法，我们在给定的 BST 中为每个节点加上比其他节点大的值，同时始终考虑 BST 的属性。

方法 - 2

1. 初始化

最初，将全局变量“sum”声明为 0。

2. 反向中序遍历

• 我们通过将 BST 递归地推送到堆栈上来对其进行后序遍历。
• 当节点被压入堆栈时，过程从堆栈顶部的节点开始，然后向下移动到右子树。

3. 访问每个节点

• 从堆栈中弹出节点。
• 通过添加当前节点的值来完成 sum 属性。
• 累积节点上的当前值。
• 处理当前节点的左子树。

4. 时间复杂度

我们的算法的运行时间也为 O(N)，其中 N 是 BST 中的节点数，确保我们只遍历每个节点一次。

5. 空间复杂度

对于使用堆栈进行遍历，空间复杂度为 O(H)，其中 H 是 BST 的高度。

Java 代码实现

输出

说明

反向中序遍历的递归调用被模拟在堆栈中，其中明确的移动是迭代的。

• 该算法的工作原理类似于递归和迭代，但没有实现递归。
• 我们通过将遍历树时遇到的所有更大值的总和加到每个节点上来修改节点的值。
• 修改后的 BST 通过 inorder 遍历方法使用 printInOrder 方法按顺序打印。

通过这种连续的循环形式，我们提供了一种快速执行操作的方法，例如将所有较大的值添加到输入 BST 的每个节点，同时保持其二叉搜索树的属性。

上述方法之间的区别

上述方法都旨在实现同一个目标：对给定二叉搜索树（BST）中的节点执行所有更大值的加法。尽管如此，它们在实现此任务的方式上有所不同。

• 递归与迭代：方法 1 提出了用于反向中序遍历的递归，而方法 2 提出了使用堆栈的迭代方法。
• 全局变量与局部变量：方法 1 提出了一个全局变量 sum，而方法 2 在策略范围内提出了一个局部变量 aggregate。
• 实现复杂度：方法 1 在执行方面更直接，因为它直接使用递归。方法 2 由于迭代方法和处理堆栈而变得有些复杂。
• 空间复杂度：这两种方法在空间复杂度上相似，都是 O(H)，因为在遍历中使用了堆栈空间，其中 H 是 BST 的级别。
• 代码构建：方法 1 将总和保持为成员变量，而方法 2 在方法内部局部地计算总和。

结论

这两种方法都旨在通过将更大值添加到每个节点来增强 BST，并通过反向中序遍历来实现。方法 1 使用递归，维护一个全局变量来存储总和，而方法 2 使用堆栈进行迭代，并使用局部变量进行聚合。尽管在实现上有所不同，但两种方法都以 O(N) 的时间复杂度和 O(H) 的空间复杂度运行，有效地增强了 BST 并保持了其属性。