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

var nodeList []*TreeNode

func Convert(pRootOfTree *TreeNode) *TreeNode {
	// 如果二叉搜索树是一棵空树直接返回空
	if pRootOfTree == nil {
		return nil
	}
	nodeList = []*TreeNode{}
	// 调用遍历二叉树函数
	inOrder(pRootOfTree)

	// 选择 nodeList 的第一个结点作为双向链表的头结点
	var head *TreeNode
	head = nodeList[0]
	// 将头结点的上一个结点置为空
	head.Left = nil
	// 定义变量 preNode 用于指向当前被遍历节点的上一个结点,初始化的时候指向头结点
	preNode := head

	// 遍历 nodeList
	for i := 1; i < len(nodeList); i++ {
		// 将 preNode 的后继结点指向当前被遍历的结点
		preNode.Right = nodeList[i]
		// 将当前被遍历结点的上一个结点指向 preNode
		nodeList[i].Left = preNode
		// preNode 向右移动
		preNode = preNode.Right
	}
	// 返回双向链表
	return head
}

// 定义递归函数中序遍历二叉搜索树，并将遍历的结果加入到一个序列中
func inOrder(curNode *TreeNode) {
	// 递归结束的条件:当前被遍历的结点为空
	if curNode == nil {
		return
	}

	// 递归处理当前结点的左子树
	inOrder(curNode.Left)
	// 处理中结点
	nodeList = append(nodeList, curNode)
	// 递归处理当前结点的右子树
	inOrder(curNode.Right)
}