将 BST 转换为更大和树

什么是 BST？

在 Python 中，“BST”是“Binary Search Tree”（二叉搜索树）的缩写。二叉搜索树是一种常见的数据结构，用于组织和存储一组元素（如数字），以便进行高效的搜索、插入、删除和遍历操作。它之所以被称为“二叉”搜索树，是因为树中的每个节点最多只有两个子节点，即左子节点和右子节点。

将 BST 转换为累加树

您可以使用反向中序遍历将二叉搜索树（BST）转换为累加树（Greater Sum Tree）。反向中序遍历按右子树、当前节点、左子树的顺序访问。在遍历过程中，您需要维护一个已遍历节点的累加和，并用这个累加和来更新每个节点的值。

方法 1

使用这种技术，树不一定需要是 BST。

步骤如下

• 逐节点遍历（前序、中序等）
• 对于每个节点，找到所有比当前节点大的节点，然后将它们的值相加。保存每个节点的这个总和。
• 按照与步骤 1 相同的顺序遍历每个节点，用其对应的总和替换每个值。

这种方法的时间复杂度为 O(n²)。

方法 2（仅使用一次遍历）

我们可以利用该树是 BST 这一特性来找到一个 O(n) 的解决方案。该方案旨在以反向中序顺序遍历 BST。通过对 BST 进行反向中序遍历，我们可以按降序获得键。在访问一个节点之前，我们已经访问了它所有更大的节点。在遍历过程中，我们跟踪键的总和，这个总和是所有大于当前节点键的键的总和。

代码

输出

Inorder Traversal of the given tree:
1 2 7 11 15 29 35 40 
Inorder Traversal of the transformed tree:
> 5
139 137 130 119 104 75 40 0 5

说明

简而言之，这段代码定义了一个二叉树和一个函数，用于根据其节点的值创建一个“累加树”。累加树是一种二叉树，其中每个节点的值都被更改为树中所有更大值的总和。代码采用递归方法来执行此转换。

1. Node 类代表二叉树中的一个节点。它有一个值（data）、一个左子节点和一个右子节点。
2. 递归的辅助函数 transformTreeUtil 执行树的实际转换。为了确保所有更大的值都被考虑在内，树以反向顺序（右、根、左）进行遍历。
3. 一个名为 transformTree 的包装函数在初始化一个全局 sum 变量后，调用 transformTreeUtil 函数来转换树。
4. printInorder 函数在中序遍历（左、根、右）树后打印节点的值。
5. 在 if __name__ == '__main__': 代码块中，打印了一个示例二叉树的原始版本和转换后的版本。

时间复杂度： O(n)，因为只对二叉树进行了一次简单的遍历，其中 n 是二叉树中节点的数量。

辅助空间： O(h)，其中 h 代表由于递归而产生的给定二叉树的高度。