LeetCode 538. 把二叉搜索树转换为累加树
题目描述
题意分析
将二叉搜索树中每个节点的值，替换为它的原值加上所有比它大的节点原值之和。只修改数值，原有左右连接保持不变，返回的仍是原根节点。
每个节点需要的不是某棵局部子树的和，而是整棵树中全部更大原值的和。利用 BST 的有序关系，按从大到小的顺序处理，就能让一个累计变量提供所有节点所需的结果。
解法：反向中序遍历累加
核心思路
[!blue]
普通中序按左、根、右访问 BST，得到从小到大的顺序；反过来按右、根、左访问，就会先处理全部更大的节点，再处理当前节点，最后处理更小的节点。
用共享变量
sum累加已经访问过的原始值。访问当前节点之前，它恰好包含所有严格大于当前原值的节点；先执行sum += node.val，再把sum写回当前节点，就得到题目要求的新值。累加必须发生在覆盖之前。尚未访问的节点仍保存原值，已访问节点即使已经改写，它的原值也已经计入
sum，不会再重复读取。后续遍历只沿原来的树结构进行，不根据修改后的值重新判断大小，因此改值不会破坏访问顺序。累计变量要贯穿整次遍历。进入左子树时，它还需要包含父节点以及此前访问过的其他较大节点，不能在每层递归重新清零。Java 在入口重置成员变量，Go 在每次函数调用内创建变量，保证不同调用不会混用旧累计值。
空节点直接结束，非空节点按右、根、左顺序完成上述操作。输入存在负值时，累计和可能减小，但只要访问顺序按原值从大到小，累计结果仍然正确，不依赖和本身单调增加。
解题步骤
- 每次入口将累计值
sum初始化为零。- 递归遇到空节点直接返回，否则先处理右子树。
- 将当前节点原值加入
sum，再令节点值等于sum。- 继续处理左子树，让更小的节点复用已经累加的所有较大值。
- 全树处理完后返回原根节点。
代码实现
class Solution {
private int sum;
public TreeNode convertBST(TreeNode root) {
// 每次入口重新累计，避免复用对象时混入旧结果
sum = 0;
dfs(root);
return root;
}
private void dfs(TreeNode node) {
if (node == null) {
return;
}
// 先访问所有更大的原值，再处理当前节点
dfs(node.right);
// sum 保存所有已经访问过的更大节点之和。
sum += node.val;
node.val = sum;
dfs(node.left);
}
}
func convertBST(root *TreeNode) *TreeNode {
sum := 0
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
// 先访问所有更大的原值，再处理当前节点
dfs(node.Right)
// sum 保存所有已经访问过的更大节点之和。
sum += node.Val
node.Val = sum
dfs(node.Left)
}
dfs(root)
return root
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点一次累加与赋值。
- 空间复杂度：$O(h)$，递归栈与树高同阶。
关键点总结
[!green]
- 当前值加严格更大值之和，才等于大于等于当前值的总和。
- 输入可以含负值，累计和不要求单调。
易错点总结
[!yellow]
- 普通中序累加得到更小值之和，方向相反。
- 先赋值再累加会读到被覆盖的数，丢失原值。
- 每层递归重新清零，会破坏整棵树共享的后缀累计。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 都利用BST中序有序性，本题改用逆中序累计更大值，原题按升序定位第k项。 |
| 897. 递增顺序搜索树 | 简单 | 同样通过有序遍历改造BST，原题改连接而保留节点值，本题改值并保留连接。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！