517. Greater Sum Tree
A charity stores donation amounts in a binary search tree and wants each node to show how much was donated in total by donors who gave at least as much as that node's own donation.
Replace the key of every node of root by the sum of all keys in the tree that are greater than or equal to it, counting every node whose key is equal to it as well, and return the root. The shape of the tree is unchanged and an empty tree stays empty. Equal keys may occur, so two nodes with the same key always receive the same new key.
Example 1
- Input:
- root = [4,2,7,1,3,5,9]
- Output:
- [25,30,16,31,28,21,9]
- Explanation:
Sums of keys that are at least as large: 9 stays 9, 7 becomes 16, 5 becomes 21, 4 becomes 25, 3 becomes 28, 2 becomes 30, 1 becomes 31.
Example 2
- Input:
- root = [3,3,null,1]
- Output:
- [6,6,null,7]
- Explanation:
Keys 3 and 3 each see 3+3=6 and the key 1 sees 1+3+3=7, giving [6,6,null,7].
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node key ≤ 1000
For every node, keys in its left subtree are ≤ its key and keys in its right subtree are ≥ its key. Equal keys may repeat. All sums fit in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)