921. Convert BST to Greater Tree

Given the root of a binary search tree, convert it to a Greater Tree so that every node's new value equals its original value plus the sum of all keys greater than it. Return the resulting tree as a level-order array. The tree is given as a level-order array.

Input: A level-order BST array.

Output: Array — the greater-sum tree in level order.

Examples

Input: [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: Each node adds all greater keys.

Input: [1]
Output: [1]
Explanation: Only node.

Input: [2,1,3]
Output: [5,6,3]
Explanation: Reverse-inorder running sum.

Constraints

• 0<=nodes<=10^4
• valid BST

Asked by