题解 | #二叉搜索树与双向链表#

思路：采用比较偷懒的方法，前面写过了中序遍历的函数，这里可以直接拿过来用。先中序遍历二叉搜索树得到排序好的切片，再根据这个切片生成双向链表。工作主要是将每个切片元素规定前驱和后继，只需要将第一个的前驱和最后一个的后继设置为nil即可。

package main
import . "nc_tools"

/**
 * 
 * @param pRootOfTree TreeNode类 
 * @return TreeNode类
*/
func Convert(pRootOfTree *TreeNode) *TreeNode {
	// write code here
    //中序遍历
	Inordertraversal := inorderTraversal(pRootOfTree)
    //根据切片生成双向链表
	node := outTreeBySlice(Inordertraversal)
    return node
}

func outTreeBySlice(input []int) *TreeNode {
	if len(input) == 0 {
		return nil
	}
	var res []*TreeNode
    //将每个切片元素从int转为TreeNode
	for i := 0; i < len(input); i++ {
		res = append(res, &TreeNode{Val: input[i]})
	}
    //后继
	for i := 0; i < len(res)-1; i++ {
		if res[i] != nil {
			res[i].Right = res[i+1]
		}
		res[len(res)-1].Right = nil
	}
    //前驱
	for i := len(res)-1; i > 0 ; i-- {
		if res[i] != nil {
			res[i].Left = res[i-1]
		}
		res[0].Left = nil
	}
	return res[0]
}
//中序遍历
func inorderTraversal(root *TreeNode) []int {
	// write code here
	var res []int
	inOrder(root, &res)
	return res
}

func inOrder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	inOrder(root.Left, res)
	*res = append(*res, root.Val)
	inOrder(root.Right, res)
}