算法篇：树之利用数组处理链表

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    // 1. 将树变成数组，利用数组的有序性
    l := preOrder(root)
    if l == nil {
        return 
    }
    // 2. 将有序数组统一构建成一个链式的树结构
    for i:=1; i< len(l);i++ { // 这里要注意的是i 从1 开始，因为我们用到了i-1做前缀
        pre,cur := l[i-1],l[i]
        pre.Left = nil
        pre.Right = cur
    }
    return 
}
func preOrder(root *TreeNode) []*TreeNode {
    if root == nil {
        return nil
    }
    res := []*TreeNode{}
    res = append(res,root)
    l := preOrder(root.Left)
    res = append(res,l...)
    r := preOrder(root.Right)
    res = append(res,r...)
    return res
}
// 算法：
// 核心思想是，先利用数据将树变成有序性，然后统一操作有序数组，进行构建

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    l := midOrder(root)
    if l == nil {
        return nil
    }
    sum := 0
    for i:=len(l)-1;i>=0;i-- {
        l[i].Val += sum
        sum = l[i].Val
    }
    return root 
}

func midOrder(root *TreeNode) []*TreeNode {
    if root == nil  {
        return nil
    }
    res := []*TreeNode{}
    l := midOrder(root.Left)
    res = append(res,l...)
    res = append(res,root)
    r := midOrder(root.Right)
    res = append(res,r...)
    return res
}