题解 | #二叉搜索树与双向链表#

二叉搜索树与双向链表：最直观的想法是，中序遍历二叉搜索树，并使用一个数组保存中序遍历的结点指针结果，再遍历中序数组将其左右相连，最后返回中序遍历数组的第一个元素即可。

vector<TreeNode*> TreeList; //中序遍历数组
//中序遍历 得到中序遍历数组
void dfs(TreeNode* cur)
{
	if(!cur)
	  return;
	dfs(cur->left);
	TreeList.push_back(cur);
	dfs(cur->right);
}
TreeNode* Convert(TreeNode* pRootOfTree) 
{
    if(!pRootOfTree) //空树
	  return nullptr;
	dfs(pRootOfTree);
	for(int i=0;i<TreeList.size()-1;i++) //遍历中序数组 左右相连
	{
	   TreeList[i]->right=TreeList[i+1];
	   TreeList[i+1]->left=TreeList[i];
	}
	return TreeList[0];
}

优化：上述方法开辟了额外的数组存储空间，那么有没有什么原地操作的方法呢？当然有！使用二叉树双指针即可！其中使用一个指针pre表示前驱结点，使用一个指针cur表示当前结点，仍然使用中序遍历方法，当左子树遍历完成后，即肯定cur->left为空才返回，此时将cur->left设置为前驱节点，同时，如果pre不为空的话，当前节点必定为前驱节点的后继节点，即pre->right=cur，当然，也要更新前驱节点为当前结点，再继续右子树的遍历，最后返回二叉树的最左下即中序遍历的开头结点即可。(其实就是中序遍历，然后在处理中间结点时，其左边指向前驱，如果前驱不为空，那么前驱的后继就指向当前，这样就避免了再遍历一次来完成后继的填充，其与数组类似，只不过是将数组转化为了指针)

TreeNode *pre=nullptr;
//中序遍历 得到中序遍历数组
void dfs(TreeNode* cur)
{
	if(!cur) //叶子结点
	  return;
	dfs(cur->left); //左子树遍历
	cur->left=pre;  //更新前驱
	if(pre) //更新后继
	  pre->right=cur;
	pre=cur; //更新下一次的前驱
	dfs(cur->right);  //右子树遍历
}
TreeNode* Convert(TreeNode* pRootOfTree) 
{
    if(!pRootOfTree) //空树
	  return nullptr;
	dfs(pRootOfTree); //中序遍历
	while(pRootOfTree->left) //找到最左下
	  pRootOfTree=pRootOfTree->left;
	return pRootOfTree; //双向链表头结点
}