#1038
Binary Search Tree to Greater Sum Tree
pupil · 370 · lc medium +23 · verified · 88.4% accepted · 4,547 likes · top 99%
Description
Given the root of a Binary Search Tree, convert it to a Greater Sum Tree by replacing each node's value with the sum of its original value and all node values greater than it in the BST.
A BST satisfies:
- Left subtree nodes have values strictly less than the node's value.
- Right subtree nodes have values strictly greater than the node's value.
- Both subtrees are also BSTs.
Example 1:
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]
Example 2:
Input: root = [0,null,1]
Output: [1,null,1]
Code
1
2
3
4
5
6
7
8
9