题目来源：. - 力扣（LeetCode）

题目思路分析

题目描述：
给定一个二叉搜索树（BST），请将其转换为一个累加树（Greater Tree），使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

思路分析：

1. 反向中序遍历：由于BST的性质，左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点。因此，我们可以利用这一特性，从右子树开始遍历（反向中序遍历），累加每个节点的值。
2. 全局变量：为了保存累加和，我们可以使用一个全局变量（或类成员变量）sum。
3. 更新节点值：在遍历过程中，累加每个节点的值到sum，然后将sum赋值给当前节点，实现累加的效果。

代码：

/**  
 * Definition for a binary tree node.  
 * struct TreeNode {  
 *     int val;  
 *     TreeNode *left;  
 *     TreeNode *right;  
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}  
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  
 * };  
 */  
class Solution {  
public:  
    int sum = 0; // 全局变量，用于保存累加和  
  
    TreeNode* convertBST(TreeNode* root) {  
        // 递归终止条件：如果节点为空，直接返回  
        if (!root) {  
            return root;  
        }  
          
        // 反向中序遍历：先遍历右子树  
        convertBST(root->right);  
          
        // 累加当前节点的值到sum，并将sum赋值给当前节点  
        sum += root->val;  
        root->val = sum;  
          
        // 再遍历左子树  
        convertBST(root->left);  
          
        // 返回转换后的树的根节点  
        return root;  
    }  
};

知识点摘要

1. 二叉搜索树（BST）：
   • 左子树所有节点的值都小于根节点。
   • 右子树所有节点的值都大于根节点。
   • 左右子树也分别为二叉搜索树。
2. 反向中序遍历：
   • 遍历顺序：右子树 -> 根节点 -> 左子树。
   • 常用于处理与BST节点值大小顺序相关的操作。
3. 全局变量与类成员变量：
   • 在递归函数中，为了保存中间结果，常常使用全局变量或类成员变量。
   • 在这里，我们使用类成员变量sum来保存累加和。

本文介绍了如何将一个二叉搜索树转换为累加树的问题。通过反向中序遍历，我们可以利用BST的性质，从右子树开始累加每个节点的值，并更新节点的值。这种方法不仅简单易懂，而且高效。通过本文的学习，你可以更好地理解BST的性质，以及如何应用递归和全局变量来解决实际问题。

在实际编程中，掌握BST的性质和遍历方法是非常重要的，它们可以帮助我们解决许多与树结构相关的问题。同时，全局变量和类成员变量的使用也是递归函数中常见的技巧，值得我们深入学习和掌握。