LeetCode 1038. 从二叉搜索树到更大和树
题目描述
题意分析
将二叉搜索树中每个节点的值改为：它原来的值，加上原树中所有比它大的节点值之和。题目节点值互不相同，因此也可理解为累加原树中所有不小于当前值的节点。
必须依据修改前的值求和，节点数量和左右连接关系保持不变，返回修改后的原根节点。改值后的树不要求继续满足二叉搜索树的大小关系。
解法：反向中序遍历累计和
核心思路
[!blue]
BST 中序遍历按值从小到大访问，将顺序反过来改成右子树、当前节点、左子树，就会按原值从大到小访问。处理当前节点时，恰好已经访问了所有比它大的节点。
用贯穿整次遍历的累计量
sum保存已访问节点的原值之和。先执行sum += node.val，把当前节点尚未修改的值加入，再执行node.val = sum，当前节点就得到自身与所有更大原值之和。之后递归左子树，刚加入的当前原值也应成为这些更小节点的贡献，因此
sum不能在子树之间重置或各自复制。空节点直接返回，不贡献数值。虽然已访问节点的值已经变了，后续遍历只沿原来的左右指针，不再靠修改后的值决定方向，也不重新读取它们计数；它们的原值贡献已经保存到
sum。只有每次处理一棵新输入树时才将累计量归零，避免复用对象带入上次结果。
解题步骤
- 在方法入口将累计和初始化为零。
- 递归遇到空节点时返回，否则先处理右子树的较大原值。
- 将当前旧值加入累计和，再把累计和写回当前节点。
- 继续处理左子树，完成后返回原根节点。
代码实现
class Solution {
private int sum;
public TreeNode bstToGst(TreeNode root) {
// 每棵输入树独立累计，避免沿用上次结果。
sum = 0;
traverse(root);
return root;
}
private void traverse(TreeNode node) {
if (node == null) {
return;
}
traverse(node.right);
// 更大的原值已累计，先加入自身旧值再写回。
sum += node.val;
node.val = sum;
traverse(node.left);
}
}
func bstToGst(root *TreeNode) *TreeNode {
// 每棵输入树独立累计，避免沿用上次结果。
sum := 0
var traverse func(node *TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
traverse(node.Right)
// 更大的原值已累计，先加入自身旧值再写回。
sum += node.Val
node.Val = sum
traverse(node.Left)
}
traverse(root)
return root
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(h)$，最坏链状为 $O(n)$。
关键点总结
[!green]
- 反向中序提供原值递减顺序，使累计和恰好包含当前值所需的全部贡献。
- 先累加旧值再覆盖，保证每个原值只贡献一次。
- 累计量在一棵树的各子树间共享，在不同输入树之间重新初始化。
- 只改节点值，遍历顺序由原树连接关系决定。
易错点总结
[!yellow]
- 先覆盖节点再累加，会丢掉它自己的原值。
- 普通的左、根、右顺序会累计较小节点，方向与题意相反。
- 在每个子树内部重新清零，会遗漏子树外已经访问的更大原值。
- Java 同一对象再次处理另一棵原始树时，需要在入口重置字段累计量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 同样利用BST的中序顺序，本题改为逆中序累计更大值，原题按升序定位第k项。 |
| 897. 递增顺序搜索树 | 简单 | 同样通过有序遍历改造BST，原题重连节点但保留值，本题修改值而保留树结构。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！