1038. Binary Search Tree to Greater Sum Tree

题目信息

题号:

1038

难度:

Medium

主题:

二叉搜索树、节点值变换、后缀和

原题:

LeetCode 1038

重点:

每个节点的新值等于原树中所有大于或等于该节点原值的节点值之和;所有计算都基于变换前的值

题目重述

给定一棵节点值互不相同的二叉搜索树。对于原值为 x 的每个节点,把它的值替换为原树中所有值大于或等于 x 的节点原值之和。

需要对整棵树完成这一变换并返回根节点。节点之间的结构保持不变;某个节点的新值不能再作为计算其他节点时的输入。

树中节点数在 [1, 100] 范围内,0 <= Node.val <= 100,所有节点值互不相同。

自建示例

较小节点累加更多原始值:

输入:root = [4,2,6,1,3,5,7]
输出:[22,27,13,28,25,18,7]
解释:原值 4 的新值为 4 + 5 + 6 + 7 = 22;原值 1 的新值为所有节点原值之和 28;原值 7 保持为 7。

只有一个值为零的节点:

输入:root = [0]
输出:[0]
解释:树中不存在其他节点,唯一节点的新值就是自身原值 0。