# 1038. Binary Search Tree to Greater Sum Tree
###### tags: `Leetcode` `Medium` `FaceBook` `DFS` `Tree Traversal`
Link: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
## 思路
把inorder Traversal反过来就可以得到答案啦
## Code
Recursive

class Solution {
    int sum = 0;
    public TreeNode bstToGst(TreeNode root) {
        reverseInorder(root);
        return root;
    }
    public void reverseInorder(TreeNode root){
        if(root==null) return;
        reverseInorder(root.right);
        sum += root.val;
        root.val = sum;
        reverseInorder(root.left);
    }
}

Iterative

class Solution {
    public TreeNode bstToGst(TreeNode root) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while(curr!=null || !stack.isEmpty()){
            while(curr!=null){
                stack.add(curr);
                curr = curr.right;
            }
            curr = stack.pop();
            sum += curr.val;
            curr.val = sum;
            curr = curr.left;
        }
        return root;
    }
}