给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。（二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。）

例如：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归算法

/**
 * Definition for a binary tree node.  # 二叉树的结构体
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int sum = 0;  # 用于存储大于当前节点的其它点的总和
public:
    TreeNode* convertBST(TreeNode* root) {
        if(root!=NULL)
        {
            convertBST(root->right);  # 反中序遍历，先找最右边的点
            sum = sum + root->val;  # 使用sum统计总和的值
            root->val = sum;  # 更新当前点的值
            convertBST(root->left);  # 再遍历左子树的节点
        }
        return root;  # 返回根节点
    }
};

解法二：迭代法，使用栈，不断迭代，将右子树的节点不断放进堆栈中，每遍历完一个右子节点，通过父节点找到左子树节点进行遍历。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;  # 用于统计比当前节点值大的所有点的值总和
        TreeNode* rt = root;  # 用于遍历所有节点
        stack<TreeNode*> stk;  # 建立一个栈，不断将节点压进堆栈中
        while(!stk.empty()|| rt != NULL)  # 迭代结束的条件是栈为空同时当前节点指向的值为null
        {
            while(rt != NULL)  # 当当前节点不为NULL
            {
                stk.push(rt);  # 寻找当前节点的右子树
                rt = rt->right;  # 遍历当前节点的右子树
            }
            rt = stk.top();  # 当遍历完所有的右子树，开始从栈最顶层开始计算
            sum += rt->val;
            rt->val = sum;
            stk.pop();
            
            rt = rt->left;
        }
        return root;
    }
};