028.把二叉搜索树转换为累加树_云泊683的博客-爱代码爱编程

题目链接：

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

大概思路：

题目要求：

给一颗二叉搜索树，把里面各个节点的值，都等于树里面，所有大于等于这个节点的，各个节点值之和。如下图，比如 7只有8大于它，累加后，7变成 7+8=15.

思路：

二叉搜索树的中序遍历左中右，其遍历的节点值，可以看成是一个升序数组，那么右中左就是降序数组，从最大值开始递减，为了方便累加，用倒序的中序遍历右中左，然后用双指针法，一个向前遍历同时累加更新数值，一个记录它上一个节点累加搜集到的数值，到遍历结束，累加树也就完成了。

递归三部曲：

1.确定递归函数参数和返回类型：

参数根节点，无返回值，这个函数就是更新数值

void traversal(TreeNode* cur) { // 右中左遍历

2.明确终止条件：

遇见空返回。

if (cur == NULL) return;

3.确定递归单层逻辑：

反中序遍历，加不断更新数值。

        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);

4.总代码：

class Solution {
private:
    int pre = 0; // 记录前一个节点的数值
    void traversal(TreeNode* cur) { // 右中左遍历
        if (cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

个人想法：

终于完结二叉树了，但只是完结而已，并没有掌握的有多深，等二刷。