Here is how I reached to this solution.
When I first look at this question, I know I can solve it by in order tree traversal, since in order traversal of BST will give us a sorted list of nodes in ascending order.
This solution has an obvious issue, after we get a list of sorted nodes, we still need to calculate the sum of all values after each nodes, then I was thinking of using some dynamic programming techniques to do backward range sum.
Wait a second, since we will need to do range sum from the back, why not just do it while traverse the tree, then the solution is obvious, just simply traverse the tree in reverse order and keep adding up the values, we can use a variable to store the current sum of all nodes start from the back.
Here are some python version of this algorithm.
class Solution(object): def convertBST(self, root): tmp, stack, total = root, , 0 while root or stack: if root: stack.append(root) root = root.right else: root = stack.pop() total += root.val root.val = total root = root.left return tmp
class Solution(object): def convertBST(self, root): self.sum = 0 def helper(root): if root.right: helper(root.right) self.sum += root.val root.val = self.sum if root.left: helper(root.left) if root: helper(root) return root
Added morris tree traversal to reduce the space complexity to O(1)
class Solution(object): def convertBST(self, root): tmp, total = root, 0 while root: if not root.right: total += root.val root.val = total root = root.left else: pred = root.right while pred.left and pred.left is not root: pred = pred.left if pred.left is root: pred.left = None total += root.val root.val = total root = root.left else: pred.left = root root = root.right return tmp