牛客 二叉搜索树与双向链表

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

解题思路：
思路1：
我们知道双向链表中，每个结点有两个指针域，一个指向前一个结点，一个指向后一个结点。而在二叉树中同样也有两个指针域，一个指向左孩子，一个指向右孩子。所以二叉树和双向链表结构上是相似的。又因为二叉搜索树中，左孩子一定小于父节点，右孩子一定能够大于父节点。所以我们可以将原先指向左孩子的指针当做是链表中指向前一个结点的指针，将原先指向右孩子的指针当做是链表中指向后一个结点的指针。如图：

题目要求转换后是有序的双向链表，因为二叉搜索树的中序遍历是有序的，所以采用中序遍历来完成。当遍历到根节点的时候，只需将根和左子树最大的一个结点链接起来，将跟结点和右子树最小的一个结点链接起来即可。如图：

按照中序遍历递归，当遍历到根结点的时候，说明此事根结点的左子树已经是有序的双向链表了，并且此时链表尾部的值为左子树的最大值。我们将其与根结点链接起来，此时根结点变成了尾部，我们知道根结点后面的节点是右子树最小的结点，将其与根结点链接起来，再继续递归即可解决问题。

代码：

class solution1
{
	TreeNode* head = nullptr;//进行链接的头
	TreeNode* realhead = nullptr;//保存双向链表的头结点
public:
	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if (pRootOfTree == nullptr)
			return nullptr;
		Convert(pRootOfTree->left);//中序遍历，左->根->右
		if (head == nullptr)
		{
			head = pRootOfTree;//head指向最左边第一个结点
			realhead = pRootOfTree;//此时在最左边的结点，此为链表的头
		}
		else{
			head->right = pRootOfTree;
			pRootOfTree->left = head;
			head = pRootOfTree;
		}
		Convert(pRootOfTree->right);
		return realhead;
	}
};

看图理解一下代码：

思路2：
同样，,由于二叉搜索树中序遍历是有序的，定义一个放结点的数组。通过中序遍历将树的结点全部放入数组中。此时数组中的结点数值是有序的。最后遍历数组将每一个节点左指针域链接到前面一个结点，右指针域链接到后面一个结点。返回数组第一个结点即可解决问题。
代码：

class Solution2 {
	std::vector<TreeNode*> v;
public:
	void Func(TreeNode* root)//中序遍历
	{
		if (root->left)
			Func(root->left);
		v.push_back(root);
		if (root->right)
			Func(root->right);
	}
	TreeNode* Convert(TreeNode* pRootOfTree)
	{
		if ((pRootOfTree == nullptr) || (!pRootOfTree->left) && (!pRootOfTree->right))
			return pRootOfTree;
		Func(pRootOfTree);
		v[0]->left = nullptr;
		v[0]->right = v[1];
		size_t i = 1;
		for (; i<v.size() - 1; i++)
		{
			v[i]->left = v[i - 1];
			v[i]->right = v[i + 1];
		}
		v[i]->left = v[i - 1];
		v[i]->right = nullptr;
		return v[0];
	}
};

思路1借鉴于：思路1