LeetCode Solutions
1038. Binary Search Tree to Greater Sum Tree
Time: $O(n)$ Space: $O(\log n)$
class Solution {
public:
TreeNode* bstToGst(TreeNode* root) {
int prefix = 0;
function<void(TreeNode*)> reversedInorder = [&](TreeNode* root) {
if (root == nullptr)
return;
reversedInorder(root->right);
root->val += prefix;
prefix = root->val;
reversedInorder(root->left);
};
reversedInorder(root);
return root;
}
};