538.md

Question:

Given 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 sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Analysis

这题是非常的不错的，作为简单的题目，到这个难度也是可以的了。 首先呢，BST中序的结果是递增数列，这题有个非常笨重的方法，就是建立一个数组，存放中序的遍历值，然后题目的要求实际就是把每个元素修改成为自身以及后面的元素的和。所以，就简单了吧。并没有实现，相信应该不难。

本题有个比较巧妙的方法，就是在中序遍历中求值，BST最大的就是最最右叶子节点，那我们就中序遍历到最最右边，到了不能再右了，其值不变，但是他的值保留到一个全局和中，以后所有节点就是自身加上这个全局和，正好变成了上面数组从后往前加和了。非常巧妙。

Tips

BST中序遍历的结果是递增的，这点很重要。 这题非常好，涉及一个二叉树累计结果的处理。

Code

func convertBSTWorker(root *TreeNode, sum *int) *TreeNode {
	if root == nil {
		return nil
	}

	convertBSTWorker(root.Right, sum)
	*sum += root.Val
	root.Val = *sum
	convertBSTWorker(root.Left, sum)

	return root
}

func convertBST(root *TreeNode) *TreeNode {
	var sum int
	convertBSTWorker(root, &sum)
	return root
}