LeetCode 538. 把二叉搜索树转换为累加树*

反向中续遍历一次即可；

个人想的是先统计总和值，然后中序遍历正向累计，减去差值；

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int cnt=sum(root);
        int s=0;
        dfs(root,s,cnt);
        return root;
    }

    int sum(TreeNode* root){
        if(!root)
            return 0;
        return root->val+sum(root->left)+sum(root->right);
    }

    void dfs(TreeNode* root,int& sum,int cnt){
        if(!root)
            return;
        dfs(root->left,sum,cnt);
        int temp=root->val;
        root->val=cnt-sum;
        sum+=temp;
        dfs(root->right,sum,cnt);
    }
};

class Solution {
public:
    int sum = 0;

    TreeNode* convertBST(TreeNode* root) {
        if (root != nullptr) {
            convertBST(root->right);
            sum += root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};