本文详细解析了如何将二叉搜索树（BST）转换为累加树（Greater Tree），即每个节点的值更新为原节点值加上所有大于或等于该节点值的总和。核心算法利用了二叉搜索树的特性，通过反向中序遍历（右-根-左）结合累加和，以递归方式高效地完成转换，并重点阐释了递归调用中累加值传递的机制。
理解累加树的转换原理
将二叉搜索树转换为累加树（Greater Tree）是指对树中的每个节点，将其值更新为原节点值加上所有大于或等于该节点值的节点之和。由于二叉搜索树的特性——左子树所有节点的值小于根节点，右子树所有节点的值大于根节点，我们可以利用这一特性进行高效的转换。
实现这一转换的关键在于采用反向中序遍历（Right -> Root -> Left）策略。当我们从右子树开始遍历时，遇到的节点值总是大于或等于其左侧的节点。因此，我们可以维护一个累加和，在遍历过程中不断更新这个和，并将其加到当前节点的值上。
核心算法解析
以下是实现累加树转换的JavaScript代码示例：
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
const bstToGst = (root) => {
// 辅助函数，用于递归遍历和更新节点值
// sum 参数用于传递当前已经累加的“更大”值之和
function go(node, sum) {
// 1. 基本情况：如果当前节点为空，则返回当前的累加和。
// 这是递归的终止条件，也是累加和向上返回的机制。
if (!node) {
return sum;
}
// 2. 遍历右子树：首先处理右子树，因为右子树中的所有节点都比当前节点大。
// go(node.right, sum) 会返回右子树遍历完成后，所有已处理的更大节点值的总和。
// 这个总和（包括右子树的所有节点和从父节点传递下来的 sum）被加到当前节点 node.val 上。
node.val += go(node.right, sum);
// 3. 遍历左子树：处理完当前节点及其右子树后，当前 node.val 已经包含了
// 自身值以及所有比它大的节点值（来自右子树和初始 sum）。
// 现在，将这个更新后的 node.val 作为新的累加和传递给左子树。
// 左子树中的所有节点都比当前 node 小，但它们需要加上当前 node 及其右子树的值。
// 因此，返回 go(node.left, node.val) 的结果，确保这个累加和继续向下传递。
return go(node.left, node.val);
}
// 从根节点开始调用辅助函数，初始累加和为0
go(root, 0);
// 返回转换后的根节点
return root;
};关键语句 return go(root.left, root.val); 的作用
在上述代码中，return go(root.left, root.val); 语句是理解累加树转换机制的核心之一。其作用可以分解为以下几点：
-
传递更新后的累加和： 当执行到这一行时，root.val 已经完成了更新。它现在包含了：
- root 节点原始值。
- 所有位于 root 右子树中的节点值（因为 go(root.right, sum) 的结果已经被加到 root.val 上）。
- 从 root 的父节点或初始调用传递下来的 sum 值（代表比 root 及其右子树所有节点都大的值）。 这个更新后的 root.val 正是 root 及其所有比它大的节点值的总和。
继续遍历左子树： 根据二叉搜索树的特性，root.left 子树中的所有节点都小于 root 节点。因此，在处理 root.left 子树时，我们需要确保这些较小的节点也能累加上 root 节点自身以及所有比 root 大的节点的值。通过将更新后的 root.val 作为新的 sum 参数传递给 go(root.left, root.val)，我们确保了左子树中的每个节点在更新时，都会包含这个“更大”的累加值。
递归调用的返回值： go 函数的返回值始终是当前子树（或整个树）遍历完成后，下一个需要累加的“更大”值之和。当 go(root.left, root.val) 执行完毕并返回时，它实际上返回的是在处理完 root 的左子树后，继续向上层（root 的父节点）或更上层传递的累加和。这个返回值最终会传递到最初的 go(root, 0) 调用，但由于我们只关心对树的修改，最终 bstToGst 函数直接返回了被修改的 root。
示例跟踪
让我们用一个例子来跟踪 sum 的传递和节点值的更新：
4
/ \
1 6
/ \ / \
0 2 5 7
\ \
3 8初始调用 go(root=4, sum=0)
-
go(4, 0):
- 调用 go(6, 0) (右子树)
-
go(6, 0):
- 调用 go(7, 0) (右子树)
-
go(7, 0):
- 调用 go(8, 0) (右子树)
-
go(8, 0):
- 调用 go(null, 0) -> 返回 0
- 8.val += 0 -> 8.val = 8
- 调用 go(null, 8) -> 返回 8
- 8 返回到 go(7, 0)
-
go(8, 0):
- 7.val += 8 -> 7.val = 15
- 调用 go(null, 15) -> 返回 15
- 调用 go(8, 0) (右子树)
- 15 返回到 go(6, 0)
-
go(7, 0):
- 6.val += 15 -> 6.val = 21
- 调用 go(5, 21) (左子树)
-
go(5, 21):
- 调用 go(null, 21) -> 返回 21
- 5.val += 21 -> 5.val = 26
- 调用 go(null, 26) -> 返回 26
- 26 返回到 go(6, 0)
-
go(5, 21):
- 26 返回到 go(4, 0)
- 调用 go(7, 0) (右子树)
- 4.val += 26 -> 4.val = 30
- 调用 go(1, 30) (左子树)
-
go(1, 30):
- 调用 go(2, 30) (右子树)
-
go(2, 30):
- 调用 go(3, 30) (右子树)
-
go(3, 30):
- 调用 go(null, 30) -> 返回 30
- 3.val += 30 -> 3.val = 33
- 调用 go(null, 33) -> 返回 33
- 33 返回到 go(2, 30)
-
go(3, 30):
- 2.val += 33 -> 2.val = 35
- 调用 go(null, 35) -> 返回 35
- 调用 go(3, 30) (右子树)
- 35 返回到 go(1, 30)
-
go(2, 30):
- 1.val += 35 -> 1.val = 36
- 调用 go(0, 36) (左子树)
-
go(0, 36):
- 调用 go(null, 36) -> 返回 36
- 0.val += 36 -> 0.val = 36
- 调用 go(null, 36) -> 返回 36
- 36 返回到 go(1, 30)
-
go(0, 36):
- 36 返回到 go(4, 0)
- 调用 go(2, 30) (右子树)
- 36 返回到初始调用
-
go(1, 30):
-
go(6, 0):
- 调用 go(6, 0) (右子树)
最终，树的节点值会被正确更新。
注意事项与总结
- 二叉搜索树特性： 此算法高度依赖于二叉搜索树的有序性。如果输入不是二叉搜索树，则结果将不正确。
- 反向中序遍历： 理解右-根-左的遍历顺序是关键。它确保了在处理当前节点时，所有比它大的节点（位于其右子树或更上层的右侧）的值已经累加到 sum 中。
- 累加和的传递： sum 参数在递归调用中起到了至关重要的作用。它不仅在向下传递时携带了已处理的更大节点值之和，而且在从递归调用返回时，也返回了当前子树处理完毕后的最新累加和，供上层节点继续使用。
-
时间与空间复杂度：
- 时间复杂度： O(N)，其中 N 是树中节点的数量。每个节点只访问一次。
- 空间复杂度： O(H)，其中 H 是树的高度。这主要是由递归调用栈的深度决定。在最坏情况下（树退化为链表），H 可以是 N。
通过深入理解反向中序遍历和累加和的传递机制，我们可以高效且优雅地将二叉搜索树转换为累加树。
