题目来源：

538：https://leetcode.cn/problems/convert-bst-to-greater-tree/description/

1038： https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/description/

 

 

C++题解1：递归法。二叉搜索树由大到小，只要将中序遍历左中右变成右中左即可。

class Solution {
public:void traversal(TreeNode*& node, int& sum) {if(!node) return;traversal(node->right, sum);sum = sum + node->val;node->val = sum;traversal(node->left, sum);return;}TreeNode* convertBST(TreeNode* root) {int sum = 0;traversal(root, sum);return root;}
};

C++题解2：迭代法。

class Solution {
public:TreeNode* bstToGst(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;int sum = 0;while(cur || !st.empty()) {if(cur) {st.push(cur);cur = cur->right;}else {cur = st.top();st.pop();sum = sum + cur->val;cur->val = sum;cur = cur->left;}}return root;}
};