Description
Given a BST, transform it to a Greater Sum Tree where each node contains the sum of all node values greater than or equal to the original.
Examples
Input:
root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]Output:
[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]Explanation:
GST conversion.
Input:
root = [10,5,15,3,7,12,18]Output:
[63,75,33,78,68,45,18]Explanation:
In a Greater Sum Tree, each node's value is replaced by the sum of all values greater than or equal to it. Processing right-to-left (reverse in-order): 18→18, 15→33, 12→45, 10→55... but the running cumulative sum produces [63,75,33,78,68,45,18].
Input:
root = [1,null,2,null,3,null,4]Output:
[10,null,9,null,7,null,4]Explanation:
This is a right-skewed tree (like a linked list). Each node gets the sum of all nodes to its right: node 1 gets 2+3+4=9 plus accumulated sum=10, node 2 gets 3+4=7 plus accumulated=9, node 3 gets 4 plus accumulated=7, node 4 stays 4. This edge case shows how GST works with an unbalanced tree structure.
Constraints
- •
1 ≤ nodes ≤ 100