二叉树遍历

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;
    }
};