A binary search tree holds distinct scores. Rewrite the tree in place so that every node's value becomes the sum of its own score and every larger score in the tree. Return the root.
Examples
4 30
/ \ / \
1 6 ==> 36 21
/ \ / \ / \ / \
0 2 5 7 36 35 26 15
\ \ \ \
3 8 33 8
Input: root = build_tree([4, 1, 6, 0, 2, 5, 7, None, None, None, 3, None, None, None, 8])
Output: tree_to_list(...) == [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]
Input: root = build_tree([2, 1, 3])
Output: [5, 6, 3]
Constraints
0 <= number of nodes <= 1000-1000 <= node.val <= 1000, all distinct
Goals
- Traverse a search tree in descending order (right, node, left)
- Carry a running total through the traversal