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

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

注意：本题和 1038: 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]
输出：[1,null,1]

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

• 树中的节点数介于 0 和 104 之间。
• 每个节点的值介于 -104 和 104 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

class Solution {
public:
//由于是遍历整棵树，而且也不改变树的结构，因此可以不用返回值
    TreeNode* dfs(TreeNode* root,int& val){
        if(!root) return nullptr;
        root->right = dfs(root->right,val); // 遍历整棵树，无需返回
        root->val += val;
        val = root->val;
        root->left = dfs(root->left,val);
        return root;
    }
    TreeNode* convertBST(TreeNode* root) {
        //很明显 右中左
        int tmp = 0;
        return dfs(root,tmp);
    }
};

//双指针，前后指针法。和上面方法类似

class Solution {
public:
    //双指针
    int pre = 0;
    void dfs(TreeNode* root){
        if(!root) return ;
        dfs(root->right);
        root->val += pre;
        pre = root->val;
        dfs(root->left);
        return ;
    }
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        return root;
    }
};