- 记录每个节点前的累加值,遍历时加上即可
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int pre = 0;
dfs(root, pre);
return root;
}
void dfs(TreeNode* root, int& pre) {
if (!root) {
return;
}
dfs(root->right, pre);
root->val += pre;
pre = root->val;
dfs(root->left, pre);
}
};