企业官网建设流程全解析

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）为同一道题。

输入输出示例

示例 1

Input: 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]

示例 2

Input: root = [0,null,1] Output: [1,null,1]

示例 3

Input: root = [1,0,2] Output: [3,3,2]

示例 4

Input: 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 做中序遍历得到的是从小到大排列的值；而按照「右—根—左」的顺序（即逆中序遍历），得到的恰好是从大到小排列的值。累加树要求每个节点的新值等于「原值 + 所有比它大的值之和」，这正等价于：从最大的节点开始，一路把已访问过的所有更大值累计和加到当前节点上。于是：

1. 先递归进入右子树，把所有比当前节点大的值累加完毕；
2. 把累计和加到当前节点上，并更新累计和；
3. 再递归进入左子树，此时左子树中的所有节点都能继承「当前节点及以上所有更大值之和」。

整个过程只需一次遍历，无需额外统计或排序，时间复杂度为 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.TreeNode

LeetCode-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. 再处理左子树（更小的值） }

函数体内的四步操作严格对应题目解题思路的「右节点 — 根节点 — 左节点」顺序：

1. 先递归右子树：因为右子树中的所有值都大于当前节点，必须先完成右子树的累加，才能拿到「所有比当前节点大的值之和」；
2. 累加到当前节点：root.Val += *sum把累计和加到当前节点上，实现「原值 + 所有更大值之和」；
3. 更新累计和：*sum = root.Val让累计和变成「当前节点的新值」，这样左子树中更小的节点在递归回来时，*sum里已经包含了所有比它大的值；
4. 最后递归左子树：左子树中所有节点都比当前节点小，它们需要继承当前这一步更新后的累计和。

以示例 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 Tree"，1038 题表述为 "Greater Sum Tree"），解题模型是同一个：逆中序遍历 + 累计和。复习时把两题合并记忆即可。

测试用例与运行验证

仓库为本题提供了完整的测试文件 1038. Binary Search Tree to Greater Sum Tree_test.go，采用「参数（para）+ 答案（ans）」的表格驱动测试结构，共覆盖 7 组用例：

测试用例的特点值得注意：

• 完整覆盖题目给出的全部 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