面试题27：二叉搜索树和双向链表

题目：

题目：输入一颗二叉搜索树，将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。比如输入如下图中左边的二叉搜索树，则输出转换之后的排序双向链表。
二叉树的定义如下：

class BinaryTreeNode{
	int mNValue;
	BinaryTreeNode mPLeft;
	BinaryTreeNode mPRight;
}

解题思路：

(1)利用中序遍历，因为中序遍历的顺序刚好是二叉搜索树的从小到大的遍历顺序。

(2)当遍历到根结点的时候，将根结点左子树结点，指向左子树中最大的元素，即双向链表中最后的一个元素。（这时候已经转化后左子树了）和将最后的元素的右子树指向根结点。这样此时遍历的根结点也是双向链表了，并将最后一个元素替换为该结点。

（3）然后如果右子树不是空的话，将右子树和链表的最后一个元素结点传到递归方法中转换。左右子树 都是这样递归转换。