36.md

二叉搜索树与双向链表

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表 要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述：二叉树的根节点 返回值描述：双向链表的其中一个头节点

示例

输入：{10,6,14,4,8,12,16}

返回值： From left to right are: 4,6,8,10,12,14,16; From right to left are: 16,14,12,10,8,6,4;

说明：输出的时候将双向链表的头节点返回即可

思路

• {二叉搜索树} + {排序的} 就想到了中序遍历
• 双向链表需要一个辅助变量放 {上一个} 即 {当前的}
• 这样遍历的下一个的时候，下一个的前一个就有着落了
• 同时前一个的后一个也安排了，后一个就是当前的
• 将 {上一个} 的后一个指针指向当前即可

实现

var result *TreeNode = &TreeNode{}
var pre = result

func Convert(pRootOfTree *TreeNode) *TreeNode {
    if pRootOfTree == nil {
        return nil
    }
	InOrder(pRootOfTree)
    result.Right.Left = nil
	return result.Right
}

func InOrder(root *TreeNode) {
	if root == nil {
		return
	}
	InOrder(root.Left)
	pre.Right = root
	root.Left = pre
	pre = root
	InOrder(root.Right)
}