题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路分析：
这道题一开始的思路是借用队列结构，首先中序遍历二叉树，按顺序保存结点，再依次出队列，创建前向后向指针。但由于题目的设定是不允许创建新的结点结构，所以考虑其他方法。
在做二叉树相关的题时，一般都利用递归完成。本题中需要用一个指向当前链表最后结点的指针来完成，对于每个新输入的树，对左子树做递归操作，保证每次都更新指向当前链表最后结点的指针，那么当完成左子树时，当前根的前向指针（左指针）就指向其左子树链表的最后一个结点，同时去判断最后这个结点是否为空，若不为空，它的后向指针（右指针）就指向当前的根。接下来就更新这个最后结点的指针指向当前的根结点，再对右子树做同样操作。
参考了一篇博客，说得相对清晰，https://cuijiahua.com/blog/2017/12/basis_26.html
代码：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* pLastNodeInList = nullptr;
ConvertNode(pRootOfTree, &pLastNodeInList); while(pLastNodeInList!=nullptr && pLastNodeInList->left!=nullptr)
{
pLastNodeInList = pLastNodeInList->left;
}
return pLastNodeInList;
} void ConvertNode(TreeNode* pRoot, TreeNode** pLastNode)
{
if(pRoot==nullptr)
return;
if(pRoot->left!=nullptr)
ConvertNode(pRoot->left, pLastNode);
pRoot->left = *pLastNode;
if(*pLastNode!=nullptr)
{
(*pLastNode)->right = pRoot;
}
*pLastNode = pRoot;
if(pRoot->right!=nullptr)
{
ConvertNode(pRoot->right, pLastNode);
}
}
};