深入理解 LeetCode 1038：利用反向中序遍历将二叉搜索树转换为累加树

本教程深入探讨 LeetCode 1038 题，讲解如何将二叉搜索树（BST）转换为累加树（Greater Tree）。核心方法是利用 BST 的特性，通过一次反向中序遍历（右-根-左）来高效更新节点值。文章将详细解析递归函数的运作机制，特别是 `return go(root.left, root.val)` 语句如何确保累加和的正确传递，并提供示例代码和解释，帮助读者掌握这一经典算法模式。

在二叉搜索树（BST）中，每个节点的值都大于其左子树中的所有节点值，且小于其右子树中的所有节点值。将 BST 转换为累加树（Greater Tree）的目标是使每个节点的新值等于其原始值加上所有大于或等于其原始值的节点值之和。例如，如果一个 BST 节点值为 X，转换后它的新值将是 X + (所有大于 X 的节点值之和)。

核心思想：反向中序遍历

解决此问题的关键在于利用 BST 的有序性。如果我们按照从大到小的顺序遍历 BST 中的所有节点，就可以在遍历过程中累加一个总和，并将这个总和加到当前节点上。这种从大到小的遍历顺序恰好是“反向中序遍历”（Right -> Root -> Left）。

1. 访问右子树： 首先访问右子树，因为右子树中的所有节点都比当前根节点大。
2. 访问根节点： 接着访问根节点。此时，我们已经处理了所有比根节点大的节点（即右子树中的节点），并累加了它们的和。我们将这个累加和加到根节点上。
3. 访问左子树： 最后访问左子树。左子树中的所有节点都比当前根节点小，但它们仍然需要加上之前累积的总和（包括根节点及其右子树的和）。

算法实现与代码解析

以下是实现这一转换的 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. 递归处理右子树：
        // 先处理右子树，并将右子树处理完后返回的累加和（即所有比当前节点大的节点值之和）
        // 加到当前节点的 val 上。
        // go(node.right, sum) 返回的是处理完右子树后，最新的累加和。
        node.val += go(node.right, sum);

        // 3. 递归处理左子树：
        // 当前节点的 val 已经更新为“原始值 + 所有比它大的节点值之和”。
        // 这个更新后的 node.val 就是新的累加和，需要传递给左子树。
        // 因为左子树中的所有节点都比当前 node 小，但它们需要加上 node 当前的累加值。
        // go(node.left, node.val) 将处理左子树，并返回处理完左子树后，最新的累加和。
        // 这个返回值将继续向上传递。
        return go(node.left, node.val);
    }

    // 从根节点开始调用辅助函数，初始累加和为 0
    go(root, 0);
    // 返回已经转换完成的根节点
    return root;
};

关键语句 return go(node.left, node.val); 详解：

AssemblyAI

转录和理解语音的AI模型

65

查看详情

理解 go 函数中 sum 参数的含义和返回值至关重要。

• sum 参数的含义： go(node, sum) 中的 sum 参数代表的是在遍历到 node 之前，所有已经处理过的、且值大于或等于 node 原始值的节点之和。换句话说，它是“当前节点右侧（或更右侧）所有节点的累加和”。
• node.val += go(node.right, sum);：
  • go(node.right, sum) 会递归地处理 node 的整个右子树。当这个调用返回时，它返回的 sum 是在处理完 node 的右子树中最右侧的节点后，累积到的总和。这个总和包含了 sum 参数的初始值以及 node 右子树中所有节点的值。
  • 将这个返回的 sum 加到 node.val 上，使得 node.val 更新为 node 的原始值加上所有比 node 大的节点值之和（包括右子树中的节点以及 sum 参数带来的更右侧的累加）。
• return go(node.left, node.val);：
  • 此时，node.val 已经包含了 node 原始值以及所有比它大的节点值之和。这个更新后的 node.val 就是新的“累加和”，它将作为参数传递给 node 的左子树。
  • go(node.left, node.val) 会递归地处理 node 的整个左子树。左子树中的每个节点都会将这个 node.val 作为其初始累加和。
  • 最终，go(node.left, node.val) 会返回处理完整个左子树后，累积到的最终总和。这个总和包含了 node 及其右子树、node 自身以及 node 左子树中所有节点的值。
  • 这个返回值正是当前 go(node, sum) 函数需要向其调用者返回的值，以继续向上传递累积的总和。它确保了整个树的遍历过程中，sum 始终代表着当前节点及其右侧所有节点的累加值，正确地传递给下一个需要更新的节点。

示例解析

让我们使用提供的示例树来追踪 bstToGst 函数的执行过程：

      4
    /   \
  1       6
 / \     / \
0   2   5   7
     \       \
      3       8

初始调用：bstToGst(root_4) 会调用 go(root_4, 0)。

1. go(root_4, 0):
   • 调用 go(root_4.right, 0)，即 go(root_6, 0)。
2. go(root_6, 0):
   • 调用 go(root_6.right, 0)，即 go(root_7, 0)。
3. go(root_7, 0):
   • 调用 go(root_7.right, 0)，即 go(root_8, 0)。
4. go(root_8, 0):
   • 调用 go(root_8.right, 0)，即 go(null, 0) -> 返回 0。
   • root_8.val += 0 (8 + 0 = 8)。root_8.val 更新为 8。
   • 调用 go(root_8.left, 8)，即 go(null, 8) -> 返回 8。
   • go(root_8, 0) 返回 8。
5. go(root_7, 0) 收到 8：
   • root_7.val += 8 (7 + 8 = 15)。root_7.val 更新为 15。
   • 调用 go(root_7.left, 15)，即 go(null, 15) -> 返回 15。
   • go(root_7, 0) 返回 15。
6. go(root_6, 0) 收到 15：
   • root_6.val += 15 (6 + 15 = 21)。root_6.val 更新为 21。
   • 调用 go(root_6.left, 21)，即 go(root_5, 21)。
7. go(root_5, 21):
   • 调用 go(root_5.right, 21)，即 go(null, 21) -> 返回 21。
   • root_5.val += 21 (5 + 21 = 26)。root_5.val 更新为 26。
   • 调用 go(root_5.left, 26)，即 go(null, 26) -> 返回 26。
   • go(root_5, 21) 返回 26。
8. go(root_6, 0) 收到 26：
   • go(root_6, 0) 返回 26。
9. go(root_4, 0) 收到 26：
   • root_4.val += 26 (4 + 26 = 30)。root_4.val 更新为 30。
   • 调用 go(root_4.left, 30)，即 go(root_1, 30)。
10. go(root_1, 30):
    • 调用 go(root_1.right, 30)，即 go(root_2, 30)。
11. go(root_2, 30):
    • 调用 go(root_2.right, 30)，即 go(root_3, 30)。
12. go(root_3, 30):
    • 调用 go(root_3.right, 30)，即 go(null, 30) -> 返回 30。
    • root_3.val += 30 (3 + 30 = 33)。root_3.val 更新为 33。
    • 调用 go(root_3.left, 33)，即 go(null, 33) -> 返回 33。
    • go(root_3, 30) 返回 33。
13. go(root_2, 30) 收到 33：
    • root_2.val += 33 (2 + 33 = 35)。root_2.val 更新为 35。
    • 调用 go(root_2.left, 35)，即 go(null, 35) -> 返回 35。
    • go(root_2, 30) 返回 35。
14. go(root_1, 30) 收到 35：
    • root_1.val += 35 (1 + 35 = 36)。root_1.val 更新为 36。
    • 调用 go(root_1.left, 36)，即 go(root_0, 36)。
15. go(root_0, 36):
    • 调用 go(root_0.right, 36)，即 go(null, 36) -> 返回 36。
    • root_0.val += 36 (0 + 36 = 36)。root_0.val 更新为 36。
    • 调用 go(root_0.left, 36)，即 go(null, 36) -> 返回 36。
    • go(root_0, 36) 返回 `36

以上就是深入理解 LeetCode 1038：利用反向中序遍历将二叉搜索树转换为累加树的详细内容，更多请关注php中文网其它相关文章！