方法一是使用递归实现,这里借助了成员变量,完成递归函数间值传递

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        travel(root);
        return root;
    }
private:
    int cur_sum = 0;
    void travel(TreeNode* root){
        if(!root) return;
        travel(root->right);
        
        root->val = (cur_sum += root->val);
        
        travel(root->left);
        
    }
};

方法二,如果不使用成员变量呢?

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int cur_sum = 0;
        travel(root,cur_sum);
        return root;
    }
private:
    void travel(TreeNode* root,int &cur_sum){
        if(!root) return;
        travel(root->right,cur_sum);
        cur_sum += root->val;
        root->val = cur_sum;
        travel(root->left,cur_sum);
        
    }
};

可以看到程序主体这里基本没有变化,只是travel函数多了一格参数,函数负责更新cur_sum变量。