题目描述：

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

实现如下：

//二叉搜索树的结构特点：根的左子树的节点值都小于根节点值，右子树的节点值都大于根节点值
//构建一个有序的双向链表可以利用left作为前驱、right作为后继
//       5
//   4      7
// 2   3  6    8
//2⇿3⇿4⇿5⇿6⇿7⇿8⇿
//root->left链接到已构建双向链表的最后一个节点
//root->right链接到右子树的最小值节点
//递归方式处理每一个root
//注意：
//1.因为最后要返回构建的双向链表的head，所以一开始就找到最小值节点。O(logn)
//2.在线测试用例为无头链表
//3.仔细思考指针赋值变化
/*节点结构体定义
struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution
{
	TreeNode *lastNode = NULL;//记录构建的双向链表的最后一个节点
	TreeNode *linkListHead = NULL;//记录所构建的双向链表的head
public:
	void findMinNode(TreeNode* pRootOfTree)//寻找双向链表的head
	{
		if (pRootOfTree == NULL) return;//防御性动作
		while (pRootOfTree != NULL)
		{
			linkListHead = pRootOfTree;
			pRootOfTree = pRootOfTree->left;
		}
	}
	void BSTToOrderTwoWayLinkList(TreeNode* pRootOfTree)
	{
		if (pRootOfTree->left != NULL)//如果左子树不为空，则继续递归
			BSTToOrderTwoWayLinkList(pRootOfTree->left);

		pRootOfTree->left = lastNode;//将root->left链接到链表的最后一个节点
		if (lastNode != NULL)//如果前驱不为空，则将前驱的right链接到root
			lastNode->right = pRootOfTree;
		lastNode = pRootOfTree;//root变为链表的最后一个节点

		if (pRootOfTree->right != NULL)//如果右子树不为空，则继续递归
			BSTToOrderTwoWayLinkList(pRootOfTree->right);
	}
	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if (pRootOfTree == NULL) return linkListHead;//防御性动作
		findMinNode(pRootOfTree);//寻找双向链表head
		BSTToOrderTwoWayLinkList(pRootOfTree);//开始递归调用
		return linkListHead;
	}
};