LeetCode-Go 题解：538. Convert BST to Greater Tree（二叉搜索树累加树转换）

LeetCode-Go 题解538. Convert BST to Greater 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 仓库中 0538.Convert-BST-to-Greater-Tree 题解文档讲解如何利用二叉搜索树BST的中序有序性在 O(n) 时间内将一棵 BST 原地转换为「累加树Greater Tree」每个节点的新值等于原树中所有大于等于该节点值之和。通过本文你将掌握「反中序遍历 累计和」这一经典手法理解其与第 1038 题Binary Search Tree to Greater Sum Tree的等价关系并看到仓库中完整的 Go 实现、测试用例与公共数据结构辅助函数。一、题目回顾与核心概念给定一棵二叉搜索树的根节点root将其转换为累加树使得每个节点的值变为「原树中大于等于该节点值的所有键之和」。作为回顾二叉搜索树满足三条约束见 README.md 原文节点左子树中的所有节点键值小于该节点键值节点右子树中的所有节点键值大于该节点键值左右子树本身也必须都是二叉搜索树。由于所有节点值唯一且输入保证是合法 BST问题可以严格表述为newVal(node) node.val sum(所有大于 node.val 的节点值)。题目注意事项中明确指出本题与 1038. Binary Search Tree to Greater Sum Tree 为同一题本仓库中两题的实现逻辑完全一致详见后文第五节对比。输入输出示例题目给出四个示例均来自 README.md数组中null表示空节点按层序展开示例输入root输出1[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]2[0,null,1][1,null,1]3[1,0,2][3,3,2]4[3,2,4,1][7,9,4,10]以示例 4 验证累加语义树中大于 1 的值有 2、3、4故节点 1 变为123410节点 2 变为2349节点 3 变为347节点 4 本身最大保持4不变。输出[7,9,4,10]与之吻合。约束条件节点数量范围[0, 10^4]允许空树节点值范围-10^4 Node.val 10^4所有节点值唯一root保证是合法二叉搜索树。二、解题思路反中序遍历与累计和2.1 利用 BST 的有序性BST 的中序遍历左-根-右产生严格递增的序列。因此大于某个节点的所有节点恰好是中序遍历中排在该节点后面的全部节点。若要求「每个节点变为原值 所有更大值之和」等价于从最大节点开始逐步向后累加。2.2 右-根-左的遍历顺序将中序遍历反转即按照「右节点 → 根节点 → 左节点」的顺序遍历恰好是从大到小访问所有节点。遍历时维护一个累计和sum先递归右子树保证先处理更大的值当前节点累加sum得到新值把sum更新为当前节点的新值再递归左子树处理更小的值。这一过程每访问一个节点就把「已累加到的更大值总和」传给下一个更小的节点最终每个节点都变成原值加上所有更大值之和。原 README.md 的解题思路部分正是这一句话的概括「按照右节点 - 根节点 - 左节点的顺序遍历并累加和即可」。由于每个节点恰好访问一次时间复杂度 O(n)空间复杂度为递归栈深度 O(h)h 为树高。2.3 手工推演示例 4树[3,2,4,1]的结构为根 3左子树根 2左孩子 1右子树根 4。访问顺序右-根-左当前值累加和访问前新值累加和访问后4右子树40443根34772左子树根27991左子树最左191010最终层序输出[7,9,4,10]与官方示例一致。三、仓库源码级实现详解核心实现位于 538. Convert BST to Greater 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 convertBST(root *TreeNode) *TreeNode { if root nil { return root } sum : 0 dfs538(root, sum) return root } func dfs538(root *TreeNode, sum *int) { if root nil { return } dfs538(root.Right, sum) root.Val *sum *sum root.Val dfs538(root.Left, sum) }3.1 代码逐段分析入口函数convertBST先做空树判断空树直接返回nil随后初始化累计和sum : 0调用dfs538进行原地改造最后返回改造后的根节点。注意这里是在原树上原地修改不申请新树空间开销仅为递归栈。辅助函数dfs538是算法的核心严格按「右 → 根 → 左」的顺序执行。递归返回后sum中保存的就是所有比当前节点大的节点值之和因此root.Val *sum后节点新值即为「原值 所有更大值之和」随后*sum root.Val让累计和包含当前节点再进入左子树。为什么用指针*int递归调用之间需要共享累计和的状态。Go 中参数按值传递若直接传int子调用对sum的修改无法反映到上层因此这里显式传入*sum指针保证每次递归返回后累计和都被正确带回。这正是本实现中值得学习的细节。3.2 关键行为小结原地转换不额外创建节点仅修改Val字段空树安全convertBST(nil)直接返回nil与约束「节点数可为 0」对应单函数分工入口负责初始化与空判断dfs负责遍历累加职责清晰、便于复用第 1038 题直接换名复用同一结构。四、测试用例验证100% 覆盖的仓库测试仓库配套测试位于 538. Convert BST to Greater Tree_test.go采用para538/ans538结构组织输入输出对共覆盖 7 组用例输入层序数组期望输出覆盖意图[3,1,NULL,0,NULL,-4,NULL,NULL,-2][3,4,NULL,4,NULL,-2,NULL,NULL,2]含负值的非平衡树[2,1][2,3]只有左子树的最小 BST[][]空树边界[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测试用例的输入输出通过两个公共辅助函数相互转换Ints2TreeNode按层序[]int切片构建二叉树使用队列逐层填充左右孩子NULL标记空位Tree2ints反向把二叉树层序展平为[]int并自动裁剪末尾多余的NULL便于与期望输出直接比较。其中的NULL哨兵值定义在 structures/TreeNode.go取值为-1 63int 类型的最小值避免与题目取值范围内的真实节点值冲突。TreeNode结构体Val、Left、Right同样定义于此TreeNode.go并通过type TreeNode structures.TreeNode别名引入题解包体现了仓库在多个题目间复用公共数据结构的组织方式。测试主函数Test_Problem538逐组执行Ints2TreeNode建树 →convertBST转换 →Tree2ints展平并打印的完整链路配合go test即可验证实现正确性与本仓库「100% test coverage」的目标一致。五、与第 1038 题的关系同一算法两个函数名题目说明中明确指出本题与 1038 题相同。对照仓库实现可以确认这一点Binary Search Tree to Greater Sum Tree.go 中的bstToGst与dfs1038与本题的convertBST与dfs538结构逐行一致同样先判空、初始化sum、按右-根-左递归累加。两题的唯一差别在于函数命名convertBSTvsbstToGst与题目措辞Greater Tree vs Greater Sum Tree算法本质完全相同。因此刷题时掌握其中一题即可直接迁移到另一题这也是本仓库把两题互相标注「同题」的原因见 0538 README 与 1038 README 的 Note。六、延伸思考其他可行解法虽然本题的标准解法是反中序遍历递归但从源码结构也可以延伸出两种常见变体供读者对照练习迭代栈实现用显式栈模拟「右-根-左」的逆中序遍历。从根出发一路压入右孩子出栈时更新累计和并转向左孩子。空间复杂度与递归相同O(h)但避免了深树场景下的栈溢出风险。Morris 反向遍历利用 BST 的线索化思想在 O(1) 额外空间内完成逆中序遍历。核心是找到当前节点在中序中的前驱此处为左子树中最右节点建立临时线索后再拆除。适合对常数空间有极致要求的场景但实现复杂度更高本题约束节点数仅10^4递归方案已完全够用。可以推断仓库选择递归方案是出于「清晰、易读、覆盖官方用例」的考量对于面试场景先给出递归版并主动补充迭代版通常是更完整的作答策略。七、小结本文围绕 LeetCode-Go 仓库的 538 题解 展开梳理了题目语义每个节点新值 原值 所有更大节点值之和核心思路利用 BST 有序性做「右-根-左」反中序遍历维护累计和原地改造仓库实现538. Convert BST to Greater Tree.go 的convertBSTdfs538注意sum以指针传递以在递归间共享状态测试佐证538. Convert BST to Greater Tree_test.go 的 7 组用例以及 structures/TreeNode.go 中Ints2TreeNode/Tree2ints/NULL的配套支持同题对照与 1038 题实现 逻辑完全一致。掌握「反中序遍历 累计和」这一模式不仅能解决 538 / 1038也可迁移到其他依赖 BST 有序性的树上问题。如需本地验证可在仓库根目录执行go test ./leetcode/0538.Convert-BST-to-Greater-Tree/ -v运行该题测试。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考