LeetCode-Go 题解 1038二叉搜索树转累加树BST to Greater Sum Tree逆中序遍历详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 leetcode/1038.Binary-Search-Tree-to-Greater-Sum-Tree/README.md 文档为主体结合仓库内完整的 Go 源码实现与测试用例讲解 LeetCode 第 1038 题「二叉搜索树转累加树」的求解原理。读完本文你将掌握如何利用二叉搜索树BST的中序有序性通过一次「右—根—左」的逆中序遍历在原树上原地完成累加转换并理解该题与第 538 题「把二叉搜索树转换为累加树」的等价关系以及本仓库配套测试框架的验证方式。题目定义Given therootof a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.给定一棵二叉搜索树的根节点将其转换为累加树Greater Sum Tree原 BST 中的每个节点的键值都被替换为「原节点值」加上「树中所有比原节点值更大的键值之和」即每个节点node的新值等于原树中大于或等于node.val的值之和。作为提醒二叉搜索树必须满足以下约束节点的左子树仅包含键小于该节点键的节点节点的右子树仅包含键大于该节点键的节点左右子树也必须是二叉搜索树。注意本题与第 538 题Convert BST to Greater Tree为同一道题。输入输出示例示例 1Input: root [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]示例 2Input: root [0,null,1] Output: [1,null,1]示例 3Input: root [1,0,2] Output: [3,3,2]示例 4Input: root [3,2,4,1] Output: [7,9,4,10]以示例 4 为例原树根节点值为 3树中比 3 大的值有 4因此新值为3 4 7值为 2 的节点比它大的值有 3 和 4新值为2 3 4 9值为 4 的节点没有比它更大的值保持4值为 1 的叶子节点比它大的值有 2、3、4新值为1 2 3 4 10最终得到输出[7,9,4,10]。数据约束树中节点数量范围为[1, 100]0 Node.val 100树中所有节点的值互不相同保证root是一棵合法的二叉搜索树。解题思路利用 BST 的有序性做逆中序遍历二叉搜索树有一个关键性质中序遍历左—根—右的结果是一个严格递增的有序序列。基于这一点题目原文的解题思路直接指出根据二叉搜索树的有序性想要将其转换为累加树只需按照右节点 — 根节点 — 左节点的顺序遍历并累加和即可。为什么这样可行因为对一棵 BST 做中序遍历得到的是从小到大排列的值而按照「右—根—左」的顺序即逆中序遍历得到的恰好是从大到小排列的值。累加树要求每个节点的新值等于「原值 所有比它大的值之和」这正等价于从最大的节点开始一路把已访问过的所有更大值累计和加到当前节点上。于是先递归进入右子树把所有比当前节点大的值累加完毕把累计和加到当前节点上并更新累计和再递归进入左子树此时左子树中的所有节点都能继承「当前节点及以上所有更大值之和」。整个过程只需一次遍历无需额外统计或排序时间复杂度为 O(n)且在原树上原地修改空间复杂度不考虑递归栈为 O(1)。仓库 Go 实现与逐行解析仓库中本题的完整实现位于 1038. Binary Search Tree to Greater Sum Tree.go代码与题解文档完全一致package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func bstToGst(root *TreeNode) *TreeNode { if root nil { return root } sum : 0 dfs1038(root, sum) return root } func dfs1038(root *TreeNode, sum *int) { if root nil { return } dfs1038(root.Right, sum) root.Val *sum *sum root.Val dfs1038(root.Left, sum) }下面对关键点做逐层拆解。类型别名复用仓库公共结构// TreeNode define type TreeNode structures.TreeNodeLeetCode-Go 仓库把通用的二叉树节点结构统一放在 structures/TreeNode.go 中type TreeNode struct { Val int Left *TreeNode Right *TreeNode }题解文件通过type TreeNode structures.TreeNode注意这里是类型别名而非新类型定义直接复用仓库公共包中的节点结构保证所有题解共用一个统一的树节点定义这也是该仓库所有二叉树题目统一的组织方式。入口函数与空树兜底func bstToGst(root *TreeNode) *TreeNode { if root nil { return root } sum : 0 dfs1038(root, sum) return root }若root nil直接返回 nil这是对空树的兜底处理sum : 0用于维护「已访问过的所有更大节点值之和」的累计器由于sum需要在递归调用之间持续共享并修改这里以指针*int的形式传入递归函数确保每次更新都能被后续调用感知转换在原树上就地完成因此递归结束后直接返回原root即可。递归核心右—根—左的逆中序累积func dfs1038(root *TreeNode, sum *int) { if root nil { return } dfs1038(root.Right, sum) // 1. 先处理右子树更大的值 root.Val *sum // 2. 累加所有比当前节点大的值 *sum root.Val // 3. 更新累计和供后续更小的节点使用 dfs1038(root.Left, sum) // 4. 再处理左子树更小的值 }函数体内的四步操作严格对应题目解题思路的「右节点 — 根节点 — 左节点」顺序先递归右子树因为右子树中的所有值都大于当前节点必须先完成右子树的累加才能拿到「所有比当前节点大的值之和」累加到当前节点root.Val *sum把累计和加到当前节点上实现「原值 所有更大值之和」更新累计和*sum root.Val让累计和变成「当前节点的新值」这样左子树中更小的节点在递归回来时*sum里已经包含了所有比它大的值最后递归左子树左子树中所有节点都比当前节点小它们需要继承当前这一步更新后的累计和。以示例 1 的树[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 → 15 → 21 → 26 → 30 → 33 → 35 → 36 → 36对应节点新值即为[30,36,21,36,35,26,15,...,33,...,8]与题目输出完全一致。复杂度分析时间复杂度O(n)每个节点恰好被访问一次空间复杂度不考虑递归调用栈时为 O(1)考虑递归深度时最坏情况如退化为链状的单侧树为 O(n)平均/平衡情况下为 O(log n)。与第 538 题的等价关系题目原文明确说明本题与第 538 题Convert BST to Greater Tree是同一道题。这一点在仓库源码中可以得到直接印证leetcode/0538.Convert-BST-to-Greater-Tree/538. Convert BST to Greater Tree.go 中的convertBST与本题的bstToGst实现逻辑完全一致第 538 题的递归辅助函数dfs538与本题的dfs1038结构完全相同都是「右—根—左」的逆中序累计。两题唯一的区别在于函数名与题目措辞538 题表述为 Greater Tree1038 题表述为 Greater Sum Tree解题模型是同一个逆中序遍历 累计和。复习时把两题合并记忆即可。测试用例与运行验证仓库为本题提供了完整的测试文件 1038. Binary Search Tree to Greater Sum Tree_test.go采用「参数para 答案ans」的表格驱动测试结构共覆盖 7 组用例输入层序数组期望输出层序数组[3,1,NULL,0,NULL,-4,NULL,NULL,-2][3,4,NULL,4,NULL,-2,NULL,NULL,2][2,1][2,3][][][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[0,NULL,1][1,NULL,1]题目示例 2[1,0,2][3,3,2]题目示例 3[3,2,4,1][7,9,4,10]题目示例 4测试用例的特点值得注意完整覆盖题目给出的全部 4 个示例确保实现与官方行为一致额外补充了空树[]与仅含两节点的边界用例第一组用例包含负值节点-4、-2超出了题目约束0 Node.val 100的范围说明测试对实现做了更严格的边界验证——即使值域放宽到负数逆中序累计的逻辑依然正确。测试运行过程中数组与树的相互转换依赖仓库公共工具函数structures.Ints2TreeNode(ints []int) *TreeNode利用层序[]int生成二叉树其中NULL定义在 structures/TreeNode.go 中值为-1 63表示空节点占位structures.Tree2ints(tn *TreeNode) []int通过队列层序遍历把树还原成数组用于断言输出。也就是说测试断言本质上是structures.Tree2ints(bstToGst(structures.Ints2TreeNode(p.one)))与期望层序数组的比对。在仓库根目录执行go test ./leetcode/1038.Binary-Search-Tree-to-Greater-Sum-Tree/或由 gotest.sh 批量执行即可验证实现正确性。延伸思考其他可行实现除仓库采用的递归逆中序遍历外本题还有两类常见的等价实现可作为理解深化显式栈的迭代逆中序由于逆中序遍历本质是「先右后左」的深度优先遍历可以用显式栈模拟递归过程从而把递归栈空间转为堆上的显式栈避免极端链状树下的递归深度风险Morris 逆中序遍历利用节点的空闲右指针建立临时回溯线索可将空间复杂度优化到真正的 O(1)无需任何栈结构。无论采用哪种写法其核心都是不变的利用 BST 中序有序性按值从大到小访问节点并累积前缀和。理解这一点本题与 538 题、乃至任何「按大小序累计前缀和」的树类问题都能迎刃而解。小结累加树转换的核心是逆中序遍历右—根—左 累计和充分利用了 BST 中序遍历的有序性仓库 Go 实现仅用bstToGst与dfs1038两个函数即可原地完成转换代码见 1038. Binary Search Tree to Greater Sum Tree.go本题与第 538 题完全等价对应实现见 leetcode/0538.Convert-BST-to-Greater-Tree可合并复习仓库测试覆盖了题目全部示例及空树、负值等边界场景验证过程依赖 structures/TreeNode.go 中的Ints2TreeNode与Tree2ints工具函数。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考