AlgoNote 题解：0538. 把二叉搜索树转换为累加树（BST 反中序遍历 + 前缀和）

• 教程
• 文档
• 知识库

本篇是「算法通关手册」AlgoNote 中 LeetCode 0538「把二叉搜索树转换为累加树」的完整题解。文章以 docs/solutions/0500-0599/convert-bst-to-greater-tree.md 为核心骨架，结合仓库中二叉搜索树与遍历章节的源码级讲解，深入剖析「反中序遍历 + 前缀和」的解法原理，并给出递归与非递归两种可运行实现。读完本文，你将掌握如何利用 BST「中序有序」的特性，把「每个节点变为原树中不小于它的一切节点值之和」这一看似复杂的树形问题，化简为一次顺序遍历中的累加问题。

1. 题目概述

题目链接：0538. 把二叉搜索树转换为累加树 - 力扣

• 标签：树、深度优先搜索、二叉搜索树、二叉树
• 难度：中等

给定一棵二叉搜索树（BST）的根节点，且二叉搜索树的节点值各不相同。要求将其转化为「累加树（Greater Tree）」，使得每个节点node的新值等于原树中大于或等于node.val的所有节点值之和。

仓库中该题解同时收录于题解总表 docs/00_preface/00_05_solutions_list.md，其同源变体 LCR 054 的完整解答见 docs/solutions/LCR/w6cpku.md，两题解法完全一致。

2. 前置知识：二叉搜索树与中序遍历

要理解本题，首先需要回顾二叉搜索树的定义（参见 docs/05_tree/05_04_binary_search_tree.md）：

• 如果左子树不为空，则左子树上所有节点值均小于它的根节点值；
• 如果右子树不为空，则右子树上所有节点值均大于它的根节点值；
• 任意节点的左、右子树也分别为二叉搜索树。

由此可得两条关键推论：

1. 左子树所有节点值 < 根节点值 < 右子树所有节点值，整棵树天然具备「左小右大」的排序结构；
2. 对二叉搜索树进行中序遍历（左 → 根 → 右），得到的节点值序列一定是严格递增的。这一点在 docs/05_tree/05_02_binary_tree_traverse.md 中有详细说明：中序遍历遵循「先左子树，后根节点，最后右子树」的递归规则，对于 BST 而言，该顺序恰好把节点按值从小到大输出。

3. 核心解题思路：把树形问题化为数组前缀和问题

3.1 问题等价转化

题目要求将每个节点的值修改为「原来的节点值 + 大于它的节点值之和」。以中序遍历视角看，BST 的中序序列是一个升序数组，例如某棵 BST 的中序序列为：

[1, 2, 3, 4, 5]

那么对节点3而言，大于或等于它的值是3 + 4 + 5；对节点1而言，是1 + 2 + 3 + 4 + 5。也就是说，问题等价于：修改升序数组中的每个元素，使其变成从该元素到数组末尾所有元素的累加和（后缀和）。

3.2 反中序遍历：右 → 根 → 左

后缀和的累加过程与中序遍历（从左到右）的顺序相反：从左往右需要「先知道后面所有数的和」，无法边遍历边求。因此我们换个思路——把左右子树交换遍历顺序，即按右 → 根 → 左的顺序遍历。

对 BST 而言，这种「反中序遍历」得到的序列恰好是降序数组。仍以上面的 BST 为例，反中序序列为：

[5, 4, 3, 2, 1]

此时我们只需用一个累加变量pre（前缀和），从左往右（即从最大值 5 开始）边走边累加：

pre = 0 访问 5：node.val += pre → 5 + 0 = 5，pre = 5 访问 4：node.val += pre → 4 + 5 = 9，pre = 9 访问 3：node.val += pre → 3 + 9 = 12，pre = 12 ...

每个节点的新值恰好等于原树中所有不小于它的值之和，且整个过程只遍历每个节点一次，累加值pre始终记录「已访问过的所有更大节点值之和」。

3.3 为什么需要pre变量

正如原文档所强调的：在计算前缀和的时候，需要用到前一个节点的值，所以需要用变量pre存储前一节点的值。pre的本质是「大于当前节点的所有节点值之和」的滚动累加器，它在每次访问节点时先被累加到当前节点上，随后更新为当前节点的新值，供下一个更小的节点使用。这一变量正是「反中序 + 前缀和」方案能在线性时间内完成转换的关键。

4. 代码实现

4.1 递归实现（原文档方案）

原文档给出的递归实现如下：

class Solution: pre = 0 def createBinaryTree(self, root: TreeNode): if not root: return self.createBinaryTree(root.right) root.val += self.pre self.pre = root.val self.createBinaryTree(root.left) def convertBST(self, root: TreeNode) -> TreeNode: self.pre = 0 self.createBinaryTree(root) return root

执行流程拆解：

1. convertBST先重置类变量pre = 0，确保每次调用相互独立；
2. 递归函数createBinaryTree以右 → 根 → 左的顺序深度优先遍历：
   • 递归终止条件：当前节点为空，直接返回；
   • 先递归右子树（处理所有更大的值）；
   • 访问当前节点：root.val += self.pre，即把「所有已遍历过的更大值之和」加到当前节点上；
   • 更新self.pre = root.val，使累加器持有当前最新（更大或相等）值的和；
   • 再递归左子树（处理更小的值）；
3. 最后返回原根节点root，整棵树被就地转换为累加树。

这种「就地修改」的方式不额外占用结果数组空间，与仓库中二叉树中序遍历的递归范式（先递归左子树 → 访问节点 → 递归右子树，见 docs/05_tree/05_02_binary_tree_traverse.md）一一对应，只是左右顺序对调。

4.2 非递归实现（显式栈）

递归实现简单直观，但在树高较大时可能受限于递归栈深度。可以改用显式栈模拟反中序遍历，逻辑完全等价：

class Solution: def convertBST(self, root: TreeNode) -> TreeNode: stack = [] # 显式栈，模拟递归过程 cur = root # 当前遍历指针 pre = 0 # 前缀和累加器 while cur or stack: # 不断向右子树深入，将沿途节点全部入栈 while cur: stack.append(cur) cur = cur.right # 此时已到达最右侧，弹出栈顶节点并处理 node = stack.pop() node.val += pre # 累加所有更大的值 pre = node.val # 更新前缀和 cur = node.left # 转向左子树 return root

非递归版本与仓库中「二叉树中序遍历的非递归实现」（while cur or stack控制循环、先压左链后弹栈、弹栈后转向右子树，见 docs/05_tree/05_02_binary_tree_traverse.md）同构，仅将「向左深入」改为「向右深入」、访问顺序相应反转，可作为面试中考察「递归与非递归转换能力」的延伸练习。

5. 复杂度分析

由于题目给定的 BST 节点值各不相同，反中序序列是严格的降序序列，因此pre累加不存在「等于值重复累加」的歧义问题；若存在相同值，按题意「大于或等于」亦可通过先累加再更新pre的同一逻辑正确处理。

6. 举一反三：同题变体与扩展阅读

• LCR 054「把二叉搜索树转换为累加树」：与本题完全相同的题目，收录于剑指 Offer 专项突破版，题解见 docs/solutions/LCR/w6cpku.md，解法可直接复用。
• 二叉搜索树的核心性质：中序遍历有序是本题一切推导的基础，完整的 BST 查找、插入、删除与有序性讨论见 docs/05_tree/05_04_binary_search_tree.md。
• 遍历体系的系统学习：递归 / 非递归的中序、前序、后序与层序遍历实现见 docs/05_tree/05_02_binary_tree_traverse.md，掌握「遍历顺序决定解题方向」的思维后，可以把本题的「反中序 + 前缀和」技巧迁移到其他依赖遍历顺序的 BST 题目中。

总结：本题的关键在于识别 BST 中序遍历的有序性，并利用「反中序遍历得到降序序列」的特性，将「后缀和」转化为可边遍历边计算的「前缀和」，配合单个累加变量pre即可在 O(n) 时间内原地完成转换。它同时展示了深度优先搜索、二叉搜索树有序性、前缀和思想三者的结合，是树类中等题的经典范式。

• 教程
• 文档
• 知识库