题目

leetcode:538
实话实说，这道题的意思是真没看懂，

代码与解析

从右面看会发现线索
可以采用右中左的顺序遍历，我采用了记录前一个节点的方式

func convertBST(root *TreeNode) *TreeNode {
    var pre *TreeNode
    var helper func (root *TreeNode)*TreeNode
    helper = func (root *TreeNode)*TreeNode{
        if root==nil{
            return root
        }
        helper(root.Right)
        if pre!=nil{
            root.Val += pre.Val
            // fmt.Println(pre.Val)
        }
        pre = root
        helper(root.Left)
        return root
    }
    return helper(root)
}

或者这样做

func convertBST(root *TreeNode) *TreeNode {
    if nil == root {
        return nil
    }
    convert(root, 0)
    return root
}

func convert(root *TreeNode, sum int) int {
    if root==nil {
        return sum
    }
    // 右面的子树用sum来接受
    sum = convert(root.Right, sum)
    sum += root.Val
    // 给当前节点赋值
    root.Val = sum
    sum = convert(root.Left, sum)
    return sum
}