LeetCode 1038. 从二叉搜索树到更大和树

2021-07-16 HGNULB 约 7 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 1038. 从二叉搜索树到更大和树

题意分析

给定一棵二叉搜索树，要把每个节点的值改成「原树中所有大于等于它的节点值之和」，然后返回改造后的树根。注意求和范围包含节点自身，不是严格大于。

输入的关键信号是「二叉搜索树」四个字：左子树所有值小于根、右子树所有值大于根，且题目保证节点值互不相同。如果丢掉这个条件，本题就退化成一道普通的求和排序题。

数据规模只有不超过 100 个节点、值域 0 到 100，怎么写都不会超时，所以出题意图显然不在优化上，而在于能否用上有序性写出一趟扫描的解法。

边界上要考虑：树可能只有一个节点，此时结果就是它自己；树可能退化成一条链，递归深度会等于节点数；累加过程中的和最大约为 100 × 100，不存在溢出问题。

还有一处容易忽略的细节：改值是原地进行的，一旦某个节点被改写，它的旧值就没了，所以访问顺序必须保证「用到某个节点旧值时它还没被改」。

解法：反向中序遍历累计和

核心思路

最朴素的做法是两趟：先把整棵树的所有值收集到一个数组里，再对每个节点重新扫一遍数组，把不小于它的值加起来写回去。逻辑没毛病，但代价是 $O(n^2)$，而且完全没用上二叉搜索树的性质，面试官看到会立刻追问。

瓶颈在于「每个节点都重新求一次和」。如果改成按值从大到小的次序去访问节点，那么访问到某个节点时，比它大的节点恰好就是前面已经访问过的那一批，它们的和只要一个变量累加就够了，不必回头再扫。

关键观察是：二叉搜索树里「先右子树、再根、最后左子树」的访问次序，产生的正是一条严格递减的值序列。这条性质把「按值排序」免费做掉了，不需要真的去排序。

由此得到贯穿全程的不变量：在即将处理节点 node 之前，变量 sum 恰好等于原树中所有大于 node.val 的节点值之和。处理动作固定为两步——先 sum += node.val，再 node.val = sum——执行完后 sum 就等于所有大于等于该节点的值之和，正好是下一个（更小的）节点所需要的前提。

这两步的先后不能换，因为题目要求的和包含节点自身；它同时也解释了为什么必须先读旧值再写新值，写早了旧值就找不回来了。

解题步骤

用一个在整趟遍历中共享的变量 sum 记录累计和，初始为 0。它必须跨递归共享（Java 用成员变量、Go 用闭包捕获），因为不变量是全局推进的，写成局部变量每层都会归零。

递归进入一个节点时先判空，空则直接返回。这一步同时兜住了空树和叶子节点的两个空孩子，让后面的逻辑不必再判空。

先递归右子树。原因是右子树里的值全都大于当前节点，必须让它们先把自己算进 sum，当前节点的不变量才成立。

回到当前节点后执行 sum += node.val，再执行 node.val = sum。先加后赋是为了把自身计入；反过来写会先把节点改成不含自身的和，再把这个和又加进 sum，值直接翻倍。

最后递归左子树。左子树的所有值都小于当前节点，它们需要的前提是「当前节点及其右侧全部已计入」，而这正是上一步做完后的状态。

遍历结束后返回原来的 root。树是原地改的，节点结构没有任何变化，返回的还是同一个根指针。

以 root = [4,1,6,0,2,5,7] 走一遍：这棵树根为 4，左孩子 1（左 0、右 2），右孩子 6（左 5、右 7）。按「右、根、左」的次序，访问序列是 7、6、5、4、2、1、0。访问 7 时 sum 由 0 变成 7，节点 7 改写为 7；访问 6 时 sum 变成 13，节点 6 改写为 13；访问 5 时 sum 变成 18，节点 5 改写为 18；访问 4 时 sum 变成 22，根改写为 22；访问 2 时 sum 变成 24，节点 2 改写为 24；访问 1 时 sum 变成 25，节点 1 改写为 25；访问 0 时 sum 仍为 25，节点 0 改写为 25。最终树为 [22,25,13,25,24,18,7]。sum 的终值 25 恰好等于原树全部节点之和 0 + 1 + 2 + 4 + 5 + 6 + 7，可以拿来当一次自检。

代码实现

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)$，其中 n 为节点数；每个节点恰好被访问一次，每次只做常数次加法和赋值。

空间复杂度：$O(h)$，h 为树高，来自递归调用栈；树平衡时约为 $O(\log n)$，退化成链时为 $O(n)$。

关键点总结

二叉搜索树的题目，第一反应应当是「哪种访问次序能把值排成有序」，本题需要降序，于是把常规次序里的左右两次递归对调即可。

「按有序次序扫描 + 一个累加变量」是一整类前缀和／后缀和问题的共同骨架，把排序这一步藏进遍历次序里就省掉了额外的 $O(n \log n)$。

原地改写结构时，必须明确「读旧值」和「写新值」的先后，一旦顺序错了错误会沿着后续节点扩散，很难从最终结果反推出问题在哪。

累加变量要跨递归共享；Java 常用成员变量，Go 常用闭包捕获，两种写法都要能在白板上默写出来。

面试视角：本题和 538 是同一道题的两个编号，答完后要主动补一句「如果不允许改动树、要求返回新树怎么办」以及「迭代版本怎么写」，用显式栈模拟这个次序是常见的追问点。

易错点总结

错误写法：先写 node.val = sum 再写 sum += node.val → 单节点树 [5] 会得到 node.val = 0 然后 sum 变成 0，返回 [0]，正确答案是 [5]。

错误写法：以为要把自身从和里剔除，写成 sum += node.val; node.val = sum - node.val; → [4,1,6] 会得到 [6,10,0]，而正确答案是 [10,11,6]，因为题目要求的和是包含自身的。

错误写法：把递归顺序写成「左、根、右」 → [4,1,6] 会得到 [5,1,11]，因为访问顺序变成升序，sum 累的是比自己小的部分，方向正好相反。

错误写法：把 sum 声明成 traverse 内部的局部变量 → 每层递归各自持有一份，右子树累出来的和传不到根，[4,1,6] 会得到 [4,1,6] 原样返回。

错误写法：Java 里把 sum 声明为成员变量却不在 bstToGst 开头重置 → 同一个 Solution 实例被判题系统连续调用多组用例时，上一组的残留和会带进下一组，本地单测通过、提交却错。

错误写法：递归里漏掉 node == null 的出口，改成在父节点判断左右孩子是否为空 → 少写一个分支就会空指针，而且两处判断容易只改一处。

错误写法：把 sum 改成递归函数的参数和返回值来回传，却在处理完当前节点后忘记把更新过的 sum 传进左子树 → [4,1,6] 的左孩子会得到 1 而不是 11，因为它拿到的还是进入根之前的旧值。

错误写法：为了「省事」先中序收集成升序数组，再从后往前求后缀和写回，但写回时仍按原来的前序次序遍历 → 值和节点对不上号，必须保证收集和写回用的是同一种次序。

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	升序遍历中比较前驱值，或传上下界
230. 二叉搜索树中第 K 小的元素	中等	升序遍历计数到第 K 个即可提前返回
426. 将二叉搜索树转化为排序的双向链表	中等	遍历中改指针，还要首尾成环
538. 把二叉搜索树转换为累加树	中等	与本题完全同题，可用作默写检查
897. 递增顺序搜索树	简单	遍历中重建成只有右孩子的链
LCR 052. 递增顺序搜索树	简单	与 897 同题，注意断开左指针
LCR 054. 把二叉搜索树转换为累加树	中等	与本题同题的另一个编号
剑指 Offer 36. 二叉搜索树与双向链表	中等	需额外维护 pre 与 head 两个指针
剑指 Offer 54. 二叉搜索树的第k大节点	简单	降序遍历计数，方向与本题一致
面试题 04.05. 合法二叉搜索树	中等	与 98 同题，需处理值的极端边界
面试题 17.12. BiNode	简单	原地改造成链表且要求 $O(1)$ 额外空间