leetcode538.把二叉搜索树转换为累加树：反向中序遍历的数值累加之道-EW帮帮网

一、题目深度解析与BST特性利用

题目描述

给定一棵二叉搜索树（BST），将其转换为累加树。累加树的定义为：每个节点的值变为原树中大于或等于该节点值的所有节点值之和。例如，原BST中节点值为5，转换后该节点值应为原树中所有大于等于5的节点值相加的结果。要求通过递归方式实现转换，且需保持树的结构不变。

BST核心特性的应用

二叉搜索树的重要性质是左子树所有节点值 < 根节点值 < 右子树所有节点值，其中序遍历结果为严格递增序列。基于此特性，我们可以发现：若按反向中序遍历（右-根-左）的顺序访问节点，每次访问到一个节点时，已遍历过的节点值均大于当前节点值，此时将已遍历节点的累计和加上当前节点值，就能得到转换后的新值，这正是解决本题的关键思路。

二、递归解法的核心实现与逻辑框架

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum;  // 用于记录累计和

    public TreeNode convertBST(TreeNode root) {
        sum = 0;  // 初始化累计和为0
        sumTree(root);  // 开始递归转换
        return root;  // 返回转换后的根节点
    }

    public void sumTree(TreeNode root){
        if(root == null){
            return;  // 递归终止条件：遇到空节点返回
        }
        sumTree(root.right);  // 先递归处理右子树
        sum += root.val;  // 将当前节点值加入累计和
        root.val = sum;  // 更新当前节点值为累计和
        sumTree(root.left);  // 再递归处理左子树
    }
}

核心设计解析

全局变量sum：
- 用于记录从右到左遍历过程中，已访问节点的数值总和。初始化为0，随着遍历的进行，不断累加节点值。
递归入口与返回：
- convertBST方法作为对外接口，初始化sum后调用sumTree方法启动递归转换，并最终返回转换后的根节点，方便外部获取整棵累加树。
递归终止条件：
- if(root == null) return;：当遇到空节点时，直接返回，结束当前递归分支，避免空指针异常。
反向中序遍历逻辑：
- sumTree(root.right);：先递归处理当前节点的右子树，确保在处理当前节点前，已将所有大于当前节点值的节点累计完毕。
- sum += root.val;：将当前节点值加入累计和sum。
- root.val = sum;：更新当前节点值为累计和，完成节点值的转换。
- sumTree(root.left);：最后递归处理当前节点的左子树，继续对左子树的节点进行转换。

三、核心问题解析：遍历顺序与数值累加逻辑

1. 反向中序遍历的必要性

普通中序遍历（左-根-右）访问节点的顺序是从小到大，而本题需要将每个节点值更新为大于等于它的所有节点值之和。若采用普通中序遍历，在访问到某个节点时，还未遍历到所有大于它的节点，无法直接计算出目标累加值。

而反向中序遍历（右-根-左）能保证：每次访问到一个节点时，所有大于该节点值的节点均已被访问并累加，此时将累计和加上当前节点值，即可得到转换后的新值。例如，对于BST中的某个节点，其右子树的所有节点值均大于它，通过先递归处理右子树，能提前完成右子树节点值的累加，再处理当前节点时就能正确更新其值。

2. 数值累加与节点更新逻辑

在递归过程中，sum变量扮演着核心角色：

右子树递归：sumTree(root.right)递归调用会不断深入右子树，将右子树中所有节点值逐步累加到sum中。
当前节点处理：
- sum += root.val;将当前节点值加入累计和sum，此时sum即为大于等于当前节点值的所有节点值之和。
- root.val = sum;直接将sum赋值给当前节点，完成节点值的更新。
左子树递归：sumTree(root.left)处理左子树时，sum已包含了当前节点及其右子树所有节点值的累加和，继续对左子树节点进行转换，保证整棵树的节点都被正确更新。

3. 递归过程中的状态传递

sum作为全局变量，在递归调用过程中保持状态的连续性。每一层递归调用结束后，sum的值会被传递到上一层，影响上层节点的计算。例如，父节点在处理时，sum已经包含了其右子树所有节点的累加和，在此基础上加上父节点自身的值，就能得到父节点转换后的正确值，实现了从下往上的累计和传递与节点更新。

四、递归流程深度模拟：以示例BST展示转换过程

假设给定如下BST：

首次递归调用：
- 从根节点4开始，调用sumTree(root)，先执行sumTree(root.right)，即递归处理右子树6。
右子树6的递归：
- 对于节点6，继续执行sumTree(root.right)，递归处理其右子树7。
- 对于节点7，其右子树为空，返回后执行sum += root.val;，此时sum = 0 + 7 = 7，再执行root.val = sum;，节点7的值更新为7。
- 接着执行sumTree(root.left)，7的左子树为空，返回。
- 回到节点6，此时sum = 7，执行sum += root.val;，sum = 7 + 6 = 13，root.val = sum;，节点6的值更新为13。
- 然后执行sumTree(root.left)，递归处理6的左子树5。
- 对于节点5，其右子树8，递归处理8，8的左右子树为空，sum = 13 + 8 = 21，8的值更新为21，返回后5的值更新为21。
回到根节点4：
- 右子树处理完毕，此时sum = 21，执行sum += root.val;，sum = 21 + 4 = 25，root.val = sum;，根节点4的值更新为25。
处理左子树1：
- 递归处理1，先处理其右子树（为空），然后sum = 25 + 1 = 26，1的值更新为26。
- 再处理1的左子树0，sum = 26 + 0 = 26，0的值更新为26。

最终转换后的累加树如下：

      25
     / \
    26  32
   /   / \
 26   32  39
       \
        39

五、算法复杂度分析

1. 时间复杂度

递归过程中，每个节点都会被访问且仅访问一次，对每个节点的操作（更新值和累加）都是常数级别的。因此，时间复杂度为O(n)，其中n为二叉树的节点数。无论树的结构如何，都需要遍历每一个节点完成转换。

2. 空间复杂度

算法的空间复杂度主要取决于递归调用栈的深度。在最坏情况下（树退化为链表），递归栈深度为O(n)；而在平衡二叉树中，递归栈深度为O(log n)。因此，空间复杂度为O(h)，其中h为树的高度。此外，代码中使用的sum变量仅占用常数级空间，对整体空间复杂度影响较小。

六、核心技术点总结：累加树转换的关键要素

反向中序遍历策略：利用BST的有序性，通过反向中序遍历，保证在处理每个节点时，能获取到所有大于等于该节点值的累计和，是实现转换的核心思路。
全局变量状态传递：借助全局变量sum记录累计和，在递归调用过程中传递状态，确保每个节点的转换都基于正确的累计值。
递归终止与遍历逻辑：严谨的递归终止条件（空节点返回）和清晰的遍历顺序（右-根-左），保证了整棵树的每个节点都能被正确转换，且不破坏树的结构。

七、常见误区与优化建议

1. 错误的遍历顺序选择

误区：采用普通中序遍历（左-根-右）或前序、后序遍历，导致在处理节点时无法获取到所有大于等于该节点值的累计和，从而无法正确转换节点值。
正确做法：始终坚持反向中序遍历，确保遍历顺序符合累加树的构建逻辑。

2. 忽略全局变量的初始化

误区：未在每次调用convertBST方法时将sum初始化为0，导致多次转换时累计和错误，影响结果准确性。
正确做法：在convertBST方法中明确对sum进行初始化，保证每次转换的独立性和正确性。

3. 优化建议：迭代实现

如果担心递归深度过深导致栈溢出问题，可以考虑使用迭代方式，借助栈数据结构模拟递归过程。通过手动管理节点的访问顺序，同样按照反向中序遍历的逻辑进行节点值的转换，将空间复杂度优化为O(n)（在最坏情况下，栈中需存储所有节点），同时避免递归栈的潜在风险，提升算法在大规模数据下的稳定性。

通过对本题递归解法的详细剖析，我们深入理解了如何利用二叉搜索树的特性和反向中序遍历，高效实现向累加树的转换。这种思路不仅在算法问题中具有典型意义，在实际的数据处理和转换场景中，对于处理有序数据的累计计算也有着重要的参考价值。

leetcode538.把二叉搜索树转换为累加树：反向中序遍历的数值累加之道