教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是「算法通关手册」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如果左子树不为空则左子树上所有节点值均小于它的根节点值如果右子树不为空则右子树上所有节点值均大于它的根节点值任意节点的左、右子树也分别为二叉搜索树。由此可得两条关键推论左子树所有节点值 根节点值 右子树所有节点值整棵树天然具备「左小右大」的排序结构对二叉搜索树进行中序遍历左 → 根 → 右得到的节点值序列一定是严格递增的。这一点在 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 访问 5node.val pre → 5 0 5pre 5 访问 4node.val pre → 4 5 9pre 9 访问 3node.val pre → 3 9 12pre 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执行流程拆解convertBST先重置类变量pre 0确保每次调用相互独立递归函数createBinaryTree以右 → 根 → 左的顺序深度优先遍历递归终止条件当前节点为空直接返回先递归右子树处理所有更大的值访问当前节点root.val self.pre即把「所有已遍历过的更大值之和」加到当前节点上更新self.pre root.val使累加器持有当前最新更大或相等值的和再递归左子树处理更小的值最后返回原根节点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. 复杂度分析维度复杂度说明时间复杂度O(n)每个节点仅被访问一次pre累加操作均为常数时间空间复杂度O(h)递归版本取决于递归调用栈深度非递归版本取决于显式栈深度最坏情况下树退化为链表为 O(n)平均为 O(h)其中 h 为树高由于题目给定的 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) 时间内原地完成转换。它同时展示了深度优先搜索、二叉搜索树有序性、前缀和思想三者的结合是树类中等题的经典范式。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解 1038二叉搜索树转累加树BST to Greater Sum Tree逆中序遍历详解LeetCode Go 题解 1038二叉搜索树转累加树BST to Greater Sum Tree逆中序遍历详解 导读 本文以 LeetCode Go示例工程LeetCode-Go 题解538. Convert BST to Greater Tree二叉搜索树累加树转换LeetCode Go 题解538. Convert BST to Greater Tree二叉搜索树累加树转换 导读 本文基于 LeetCode Go示例工程LeetCode 0449 序列化和反序列化二叉搜索树前序遍历 BST 特性实现紧凑编码LeetCode 0449 序列化和反序列化二叉搜索树前序遍历 BST 特性实现紧凑编码 导读 本篇技术指南围绕「算法通关手册」仓库中 0449. 序列化教程文档知识库上一篇APK安装器终极指南如何在Windows电脑上轻松安装安卓应用下一篇Cursor Free VIP完整指南三步解决试用限制永久免费使用AI编程助手创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考