我来给你讲解 LeetCode 第 538 题「把二叉搜索树转换为累加树」。

题目描述

给定一个二叉搜索树（BST）的根节点，将其转换为累加树（Greater Tree），使得每个节点的值变成原树中所有大于或等于该节点值的和。

注意：二叉搜索树满足：左子树节点值 < 根节点值 < 右子树节点值。

示例：

输入: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

解题思路

第一步：理解题目要求

在累加树中，每个节点的新值 = 该节点原始值 + 所有比它大的节点值之和。

由于二叉搜索树的中序遍历是升序序列，那么如果我们进行反向中序遍历（右-根-左），遍历顺序就是从大到小的。

第二步：关键洞察

如果我们按照从大到小的顺序遍历节点，那么在处理当前节点时：

• 所有比当前节点值大的节点都已经被处理过了
• 我们可以维护一个累加变量，记录已经遍历过的节点值之和

这样，当前节点的新值 = 当前节点原始值 + 之前所有更大节点的值之和。

第三步：算法步骤

1. 初始化一个累加变量 sum = 0
2. 进行反向中序遍历（右子树 → 根节点 → 左子树）：
   • 遍历右子树（更大的值）
   • 更新当前节点值：node.val = node.val + sum
   • 更新累加变量：sum = node.val（因为现在node.val已经是新值）
   • 遍历左子树（更小的值）

第四步：详细示例

以二叉搜索树 [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 为例：

反向中序遍历顺序：8 → 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0

处理过程：

• 节点8：新值 = 8 + 0 = 8，sum = 8
• 节点7：新值 = 7 + 8 = 15，sum = 15
• 节点6：新值 = 6 + 15 = 21，sum = 21
• 节点5：新值 = 5 + 21 = 26，sum = 26
• 节点4：新值 = 4 + 26 = 30，sum = 30
• 节点3：新值 = 3 + 30 = 33，sum = 33
• 节点2：新值 = 2 + 33 = 35，sum = 35
• 节点1：新值 = 1 + 35 = 36，sum = 36
• 节点0：新值 = 0 + 36 = 36，sum = 36

第五步：代码实现

def convertBST(root):
    sum = 0
    
    def reverse_inorder(node):
        nonlocal sum
        if not node:
            return
        
        # 先遍历右子树（更大的值）
        reverse_inorder(node.right)
        
        # 处理当前节点
        sum += node.val
        node.val = sum
        
        # 再遍历左子树（更小的值）
        reverse_inorder(node.left)
    
    reverse_inorder(root)
    return root

第六步：复杂度分析

• 时间复杂度：O(n)，需要遍历每个节点一次
• 空间复杂度：O(h)，其中h是树的高度，主要是递归栈的空间

第七步：迭代解法（可选）

也可以使用迭代方法实现反向中序遍历：

def convertBST(root):
    stack = []
    current = root
    sum = 0
    
    while stack or current:
        # 一直往右走
        while current:
            stack.append(current)
            current = current.right
        
        # 处理节点
        current = stack.pop()
        sum += current.val
        current.val = sum
        
        # 转向左子树
        current = current.left
    
    return root

这种方法避免了递归的系统栈开销，更适合深度很大的树。

这个算法的核心思想就是利用BST的性质，通过反向中序遍历来实现累加计算。