刷刷刷 Day 23 | 538. 把二叉搜索树转换为累加树

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

LeetCode题目要求

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

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

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

示例

输入：[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]

解题思路

本题的关键在于理解什么是累加树，题目中提到的 “ 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和”
如下图，即从最后一个元素开始，如 8 新值不变，8 的前一个节点 7 的新值就会变化为 8(大于7) + 7 = 15， 依次类推。
再简单的理解下就是 二叉搜索树 是一个有序递增数组，如 [1,2,3] 的累加就是 [6, 5, 3]
要做累加，那就要完成右中左顺序的累加遍历操作

上代码

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        // 递归，右中左的顺序， 节点不为空就一直递归
        if (root != null) {
            // 右节点
            convertBST(root.right);
            //  中节点取值累加
            sum += root.val;
            // 累加值重新赋值给 root
            root.val = sum;
            // 左节点
            convertBST(root.left);
        }
        return root;
    }
}

重难点

理解累加
附：学习资料链接