【LeetCode刷题日记】538.把二叉搜索树转换为累加树

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，今天提前进入到我们的每日刷题环节，同时也是二叉树相关的最后一个题目，但是不知道这些题目够不够应对面试的，后面可能还会继续拓展一些题目，之后再更新一些模板解题思路，通用的，欢迎大家一起见证！

题目摘要：

538题要求将二叉搜索树转换为累加树，每个节点的新值等于原值加上所有大于该节点值的和。解题思路是利用反序中序遍历（右→根→左），维护累加和sum。递归法通过全局变量sum实现；迭代法借助栈模拟递归；Morris遍历则优化空间至O(1)。关键点：BST的中序性质与降序累加逻辑的巧妙结合。三种解法均保持O(n)时间复杂度，空间复杂度分别为O(h)、O(h)、O(1)。该题展现了二叉树遍历的灵活应用与空间优化技巧。

题目背景：538.把二叉搜索树转换为累加树

给出二叉搜索树的根节点root，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），将其转换为一个更大的树，使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键小于节点键的节点。
• 节点的右子树仅包含键大于节点键的节点。
• 左右子树也必须是二叉搜索树。

注意：本题和 1038: 1038. 从二叉搜索树到更大和树 - 力扣（LeetCode） 相同

示例 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：

输入：root = [0,null,1]输出：[1,null,1]

示例 3：

输入：root = [1,0,2]输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]输出：[7,9,4,10]

提示：

• 树中的节点数介于0和104之间。
• 每个节点的值介于-104和104之间。
• 树中的所有值互不相同。
• 给定的树为二叉搜索树。

题目解析：

刚拿到这个题目，我们先看看题目要求，题目说的很明白，将二叉搜索树转换成累加树，二叉搜索树自然不用多说，前面我们已经介绍了很多，也足够了解了

至于累加树，我们自己不知道，但是题目给我们说明了，累加树的意思就是将原本二叉搜索树的每个节点进行相应的累加，累加树每个节点的值=原本二叉搜索树的节点的值+比原来节点值大的节点的总和。

那我们该怎么累加呢，该怎么找到比该节点值大的值呢，首先由于是二叉搜索树，分辨节点值的大小其实很简单，那累加的操作呢，看着似乎很麻烦

其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

为什么变成数组就是感觉简单了

因为数组大家都知道怎么遍历，从后向前，挨个累加就可以了，这换成了二叉搜索树，看起来就别扭了一些。

BST 的中序遍历是升序序列（左→根→右）

累加树的要求：每个节点的新值 = 所有 ≥ 该节点值的节点值之和

换句话说，如果我们按照降序（右→根→左）遍历 BST：

• 遍历到的第一个节点（最大值）→ 累加和 = 它本身

• 第二个节点 → 累加和 = 它本身 + 上一个节点的累加和

• 第三个节点 → 累加和 = 它本身 + 前面所有节点的累加和

结论：使用反序中序遍历（右→根→左），维护一个累加和sum，每访问一个节点就更新它的值。

整体的逻辑我们分析的差不多了，下面我们来看看具体的实现：

1. 初始化全局变量sum = 0，用于记录已经遍历过的节点值之和

2. 递归遍历：先遍历右子树 → 处理当前节点 → 再遍历左子树

3. 处理当前节点时：

   • sum += root.val

   • root.val = sum

4. 返回根节点

递归法图解示例

输入：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] text 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8

反序中序遍历顺序（右→根→左）

转换后的树

text 30 / \ 36 21 / \ / \ 36 35 26 15 \ \ 33 8 验证：对于节点 4，原始 ≥4 的节点有 {4,5,6,7,8}，和 = 4+5+6+7+8 = 30 ✅

迭代法的具体流程：

示例树 text 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8示例树

反序中序遍历顺序（右→根→左）：

8 → 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0

详细解释

java while (cur != null || !stack.isEmpty()) { // 内层while：只负责把"当前节点及所有右子节点"压栈 while (cur != null) { stack.push(cur); cur = cur.right; // 一直往右走 } // 弹出栈顶（处理当前节点） cur = stack.pop(); sum += cur.val; cur.val = sum; // 外层while负责：转向左子树 cur = cur.left; // ← 这里！ }

图解分工

以节点4为例：

text 4 ← cur 在这里 / \ 1 6

内层 while 做的事：

text cur=4 → 压入4 → cur=6 cur=6 → 压入6 → cur=7 cur=7 → 压入7 → cur=8 cur=8 → 压入8 → cur=null

结果：stack = [4,6,7,8]（右链全部入栈）

外层 while 做的事：

text 弹出8 → 处理8 → cur = 8.left = null 弹出7 → 处理7 → cur = 7.left = null 弹出6 → 处理6 → cur = 6.left = 5 ← 转向左子树！

关键：当处理完节点6后，cur = 5，下一轮循环的内层while又会把节点5及它的右子节点（5.right=null）压栈。

完整流程图

text 初始: cur=4 │ ▼ ┌─────────────────────────────────┐ │ 内层while: 压入4→6→7→8 │ │ stack=[4,6,7,8], cur=null │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出8, 处理8, cur=8.left=null │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出7, 处理7, cur=7.left=null │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出6, 处理6, cur=6.left=5 │ ← 转向左子树 └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 内层while: 压入5, cur=5.right=null│ │ stack=[4,5], cur=null │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出5, 处理5, cur=5.left=null │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出4, 处理4, cur=4.left=1 │ ← 转向左子树 └─────────────────────────────────┘ │ ▼ 继续处理左子树...

总结

一句话记忆：

• 内层 while = 压右链

• cur = cur.left = 转左子树

两者配合，完美实现右→根→左的遍历顺序。

题目答案：

递归法：

class Solution { private int sum = 0; // 累加和 public TreeNode convertBST(TreeNode root) { if (root == null) { return null; } // 先遍历右子树（处理更大的值） convertBST(root.right); // 处理当前节点 sum += root.val; root.val = sum; // 再遍历左子树（处理更小的值） convertBST(root.left); return root; } }

迭代法（使用栈）

java class Solution { public TreeNode convertBST(TreeNode root) { if (root == null) return null; Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; int sum = 0; // 反序中序遍历：先遍历右子树 while (cur != null || !stack.isEmpty()) { // 将右子树全部入栈 while (cur != null) { stack.push(cur); cur = cur.right; } // 处理当前节点 cur = stack.pop(); sum += cur.val; cur.val = sum; // 转向左子树 cur = cur.left; } return root; } }

Morris 遍历（空间 O(1)）

java class Solution { public TreeNode convertBST(TreeNode root) { int sum = 0; TreeNode cur = root; while (cur != null) { // 如果有右子树，找到右子树的最左节点 if (cur.right != null) { TreeNode prev = cur.right; while (prev.left != null && prev.left != cur) { prev = prev.left; } if (prev.left == null) { // 建立线索 prev.left = cur; cur = cur.right; } else { // 第二次访问当前节点 prev.left = null; // 断开线索 sum += cur.val; cur.val = sum; cur = cur.left; } } else { // 没有右子树，直接处理当前节点 sum += cur.val; cur.val = sum; cur = cur.left; } } return root; } }

复杂度分析

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！