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. 所有大于等于节点的值之和