538. 把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

image.png

package leetcode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
// 思路:
//  二叉搜索树具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
//  则每个节点的值加上它的右子树所有节点的值 = 原来的节点值加上所有大于它的节点值之和
//  则遍历每个节点的右子树即可
func convertBST(root *TreeNode) *TreeNode {

    rightVals := 0
    convertBSTRight(root, &rightVals)
    return root
}

func convertBSTRight(root *TreeNode, vals *int) {

    if root == nil {
        return
    }
    convertBSTRight(root.Right, vals)

    root.Val += *vals
    *vals = root.Val
    convertBSTRight(root.Left, vals)

}