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

🚩传送门：力扣题目

题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree）。

示例 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]

解题思路：递归

使用 后续遍历 ，用 记录前项的累加和，当前结点等于 ，接着使用 更新 ，完成后续的递归遍历计算

复杂度分析

时间复杂度：，其中 是二叉搜索树的节点数。每一个节点恰好被遍历一次。

空间复杂度：,为递归过程中栈的开销，平均情况下为，最坏情况下树呈现链状，为 。

官方代码

class Solution {
    int pre = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        pre = 0;
        convertBST_(root);
        return root;
    }
    public void convertBST_(TreeNode root) {
        if(root==null)return;
        convertBST_(root.right);
        root.val += pre;
        pre = root.val;
        convertBST_(root.left);
    }
}