Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
we can use a variable to acuumulate the value passed from his father. Because for the left tree, it need the root and its right tree's value. And for the root it only need accumulate its right tree and the value passed from his father. Let me try. This idea has some issue. Because its we want to accumulate the right value to the final res, but right value also need to accumulate the sum, thus we shall return right without res.
I don't know. Let me see the std;
the idea is basically same as mine. Just remember we only need to push the root & right value to the its left as a sum value. And return a sum value as the sum of the sub tree to its father. AC!