538. Convert BST to Greater Tree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private static class State {
        private int preVal;
    }

    public TreeNode convertBST(TreeNode root) {
        State state = new State();
        dfs(state, root);
        return root;
    }

    private void dfs(State state, TreeNode root) {
        if (root == null) {
            return;
        }

        dfs(state, root.right);
        root.val += state.preVal;
        state.preVal = root.val;
        dfs(state, root.left);
    }
}

References

538. Convert BST to Greater Tree
1038. Binary Search Tree to Greater Sum Tree
剑指 Offer II 054. 所有大于等于节点的值之和