leetcode 1038. Binary Search Tree to Greater Sum Tree
题目：https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
将一棵二叉树的每个节点的值变为，原有值+原树中所有值大于此节点值的节点的值的和。
例子：
题目很绕，实际上就是利用二叉树的性质：左子树的值都比根节点小，右子树的值都比根节点的大。修改节点的顺序应该是右子树->根节点->左子树，所以遍历顺序为右根左。
这个题目的通过率很高，因为没有边界条件，一旦通过了例子，就能ac。
我的实现如下：
/**
* 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* bstToGst(TreeNode* root) {
if (!root) return root;
unordered_set<TreeNode*> viewed;
int sum = 0;
stack<TreeNode*> treestack;
treestack.push(root);
while (!treestack.empty()){
TreeNode* p = treestack.top();
if (p->right && viewed.find(p->right) == viewed.end()){
treestack.push(p->right);
}else if (viewed.find(p)==viewed.end()){
p->val += sum;
sum = p-> val;
viewed.insert(p);
if (p->left){
treestack.push(p->left);
}else{
treestack.pop();
}
}else
treestack.pop();
}
return root;
}
};
原文：https://www.cnblogs.com/vimery/p/11588204.html