#538
Convert BST to Greater Tree
pupil · 540 · lc medium +28 · verified · 71.4% accepted · 5,404 likes · top 80%
Description
Given the root of a Binary Search Tree (BST), transform it into a Greater Sum Tree: replace every node's value with the sum of its original value plus all BST values that are strictly greater than it. Return the modified tree.
Recall the BST property:
- The left subtree of each node holds values strictly smaller than the node.
- The right subtree holds values strictly larger.
- Both subtrees are also valid 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