538. 把二叉搜索树转换为累加树

题目链接（中等）

题目描述

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

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

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

注意：本题和 1038. 从二叉搜索树到更大和树 相同。

数据范围：

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

示例

示例 1：

输入： root = [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]

核心思路

题目要求：每个节点的新值 = 原值 + 所有比它大的节点值之和。

BST 的关键性质：中序遍历（左 → 根 → 右）得到升序序列。

反过来，反序中序遍历（右 → 根 → 左）得到降序序列。

降序序列正好满足「从大到小依次访问」，因此可以一边遍历一边累加：

1. 用一个变量 total 记录「已经访问过的节点值之和」（也就是所有比当前节点大的值之和）；
2. 访问当前节点时，total += node.val，然后 node.val = total；
3. 继续遍历。

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

为什么这样正确？

• 反序中序遍历的顺序是从最大到最小；
• 访问某个节点时，total 已经包含了所有比它大的节点值；
• 把 total 累加到当前节点，正好满足题目要求。

---

方法一：递归反序中序遍历

思路及解法

用递归实现反序中序遍历，用一个外部变量 total 记录累加和。

递归过程：

1. 递归右子树；
2. 处理当前节点：total += node.val，node.val = total；
3. 递归左子树。

例子：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

中序升序序列：[0, 1, 2, 3, 4, 5, 6, 7, 8]
反序降序序列：[8, 7, 6, 5, 4, 3, 2, 1, 0]

依次累加：

访问节点	total	node.val 更新为
8	8	8
7	15	15
6	21	21
5	26	26
4	30	30
3	33	33
2	35	35
1	36	36
0	36	36

最终得到 [30, 36, 21, 36, 35, 26, 15, ..., 33, ..., 8]，与题目输出一致。

代码

class Solution:
    def convertBST(self, root: TreeNode | None) -> TreeNode | None:
        total = 0

        def dfs(node: TreeNode | None) -> None:
            nonlocal total
            if not node:
                return
            dfs(node.right)          # 先访问右子树（更大的值）
            total += node.val
            node.val = total         # 更新当前节点为累加值
            dfs(node.left)           # 再访问左子树

        dfs(root)
        return root

复杂度分析

• 时间复杂度：$O(n)$，每个节点恰好访问一次。
• 空间复杂度：$O(n)$，递归栈深度最坏为 $n$（链状树），平均为 $O(\log n)$。

---

方法二：Morris 遍历（$O(1)$ 空间）

思路及解法

Morris 遍历的核心思想：利用树中大量空闲的指针（叶子节点的空指针），在 $O(1)$ 额外空间内完成中序遍历。

反序中序遍历的 Morris 规则（右 → 根 → 左）：

1. 若当前节点 node 的右子节点为空：
   • 处理当前节点（更新 total 和 node.val）；
   • 向左走：node = node.left；
2. 若当前节点的右子节点不为空：
   • 找到当前节点右子树的最左节点 succ（即反序中序遍历的「前驱」）；
   • 若 succ.left 为空：将 succ.left = node（建立线索），然后向右走：node = node.right；
   • 若 succ.left 不为空：说明线索已经用过，恢复 succ.left = None，处理当前节点，然后向左走：node = node.left。

为什么要建立线索：

• 反序中序访问某个节点之前，需要先访问它的右子树；
• 访问完右子树后，需要回到当前节点；
• 如果没有父指针，无法返回；
• Morris 用「右子树的最左节点的 left 指针」指向当前节点，作为返回的「线索」；
• 访问完后再清空这个线索，恢复树的结构。

代码

class Solution:
    def convertBST(self, root: TreeNode | None) -> TreeNode | None:
        def get_successor(node: TreeNode) -> TreeNode:
            """找到 node 右子树的最左节点"""
            succ = node.right
            while succ.left and succ.left != node:
                succ = succ.left
            return succ

        total = 0
        node = root

        while node:
            if not node.right:
                # 右子节点为空：处理当前节点，向左走
                total += node.val
                node.val = total
                node = node.left
            else:
                succ = get_successor(node)
                if not succ.left:
                    # 建立线索：succ.left 指向 node
                    succ.left = node
                    node = node.right
                else:
                    # 线索已用完，恢复并处理当前节点
                    succ.left = None
                    total += node.val
                    node.val = total
                    node = node.left

        return root

复杂度分析

• 时间复杂度：$O(n)$，每个节点最多被访问两次（一次建立线索、一次处理）。
• 空间复杂度：$O(1)$，只使用常数个指针。

---

两种方法对比

方法	时间	空间	特点
递归反序中序	$O(n)$	$O(n)$	代码极短，思路最直观
Morris 遍历	$O(n)$	$O(1)$	空间最优，但实现稍复杂

推荐：

• 面试：首选递归反序中序，代码极简，思路清晰；
• 进阶：如果面试官要求 $O(1)$ 空间，再写 Morris 遍历，展示对树结构的深入理解。

---

关键细节

1. 为什么反序中序就能解决问题

• 中序（左 → 根 → 右）得到升序序列；
• 反序中序（右 → 根 → 左）得到降序序列；
• 降序正好对应「从大到小」，访问当前节点时，前面访问过的都是更大的值，total 就是「比当前节点大的所有值的和」。

2. total 的更新顺序

total += node.val
node.val = total

必须先 +=，再赋值。这样 total 包含了当前节点的原值，node.val 得到的就是「比它大的和 + 它自己」。

3. 修改节点值 vs 返回新树

题目允许原地修改，所以直接 node.val = total 即可。如果要求返回新树，需要创建新节点，但本题不需要。

4. Morris 遍历的线索机制

• succ.left 从 None 变为 node：表示「访问完右子树后回到 node」；
• succ.left 从 node 变回 None：表示「线索已完成使命，恢复原状」；
• 通过这种「建立线索 → 使用线索 → 清除线索」的方式，实现 $O(1)$ 空间遍历。

注意：Morris 遍历结束后，整棵树的结构恢复原样，只是节点值被更新了。

5. 与 LC 1038 的关系

LC 538 和 LC 1038 是同一道题，只是题号不同。代码完全通用。

---

总结

• 核心思路：BST 反序中序遍历得到降序序列，边遍历边累加；
• 反序中序：右 → 根 → 左；
• 递归法：
  • 用外部变量 total 记录累加和；
  • 访问节点时 total += node.val，node.val = total；
  • 时间 $O(n)$、空间 $O(n)$；
• Morris 遍历：
  • 利用右子树最左节点的空 left 指针作为线索；
  • 时间 $O(n)$、空间 $O(1)$；
• 通用套路：BST 的题目 → 想到中序遍历的有序性；本题就是「反序中序遍历 + 累加」。

相关题目

• LC 1038. 从二叉搜索树到更大和树（本题的另一题号）
• LC 230. 二叉搜索树中第 K 小的元素（中序遍历）
• LC 98. 验证二叉搜索树（中序遍历 + 递增性）
• LC 108. 将有序数组转换为二叉搜索树（二分 + 构建）
• LC 94. 二叉树的中序遍历（Morris 遍历的基础）