题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

    4
   / \
  2   5
 / \
1   3

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
Leetcode链接：剑指offer面试题36：二叉搜索树与双向链表

算法分析

  • 由于中序遍历二叉搜索树可以得到一个递增的序列，所以本题可以考虑在中序遍历的过程中将二叉树转化为双向链表。其中pLastNode指向最终的双向链表的最后一个节点
  • 由于golang的参数传递只能是值传递，所以在函数内修改指针的指向并不能影响函数外指针的指向，所以指向pLastNode可以考虑使用全局变量或者定义为二重指针（本题解使用的是全局变量）。

Golang代码如下

type BinaryTreeNode struct {
	val interface{}
	Left, Right *BinaryTreeNode
	Parent *BinaryTreeNode
}

var pLastNode *tree.BinaryTreeNode

func InOrder(pNode *tree.BinaryTreeNode) {
	if pNode.Left != nil {
		InOrder(pNode.Left)
	}

	pNode.Left = pLastNode
	if pLastNode != nil {
		pLastNode.Right = pNode
	}
	pLastNode = pNode

	if pNode.Right != nil {
		InOrder(pNode.Right)
	}
	return
}

func treeToDoublyList(root *tree.BinaryTreeNode) *tree.BinaryTreeNode {
	if root == nil {
		return nil
	}
	//	得到的双向链表中，left指向前驱结点，right指向后继节点
	InOrder(root)
	pHead := pLastNode
	for pHead.Left != nil {
		pHead = pHead.Left
	}
	pHead.Left = pLastNode
	pLastNode.Right = pHead
	return pHead
}