给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

解答1：

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        greaterTree(root, 0);
        return root;
    }

    int greaterTree(TreeNode* root, int addvalue) {
        if(!root) return 0;
        int res = 0;
        res += root->val;
        root->val += addvalue;
        if(root->right) {
            addvalue = greaterTree(root->right, addvalue);
            root->val += addvalue;
            res += addvalue;
        }
        if(root->left) {
            res += greaterTree(root->left, root->val);
        }
        return res;
    }
};

解答2：

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return root;
        stack<TreeNode*> s;
        TreeNode* p = root;
        int addvalue = 0;
        while(p || !s.empty()) {
            if(p) {
                s.push(p);
                p = p->right;
            }
            else {
                // p == nullptr
                p = s.top();
                s.pop();
                p->val += addvalue;
                addvalue = p->val;
                p = p->left;
            }
        }
        return root;
    }
};

思路：

这道题我首先采用的是传统的根据二叉搜索树的特征递归累加的方法。每个节点被更新的值为：自己的值+右子树的值+X。其中X=父节点的值if当前结点是父节点的左子节点；X=父节点的父节点的值if当前结点是父节点的右子节点。这里的前提条件是父节点及祖先节点的权值已被更新。使用传参的方式来解决这一问题：遍历左结点的时候将自身更新后的权值传入，遍历右结点的时候将自己的父结点的权值传入。在本身的遍历中加上传入的权值即可完成X值的更新工作。

此外，将二叉搜索树由大到小遍历，并将大值累加到小值的思路更加简洁。我们使用reverse的中序遍历即右-中-左遍历即可完成由大到小遍历。这时候从大到小依次更新权值，每次更新只需要将比其序大1的结点的权值加到自身，即可实现这一目标，因为更新后每个结点的权值都是累加值。