题目描述：

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

思路分析：

这道题一开始的思路是借用队列结构，首先中序遍历二叉树，按顺序保存结点，再依次出队列，创建前向后向指针。但由于题目的设定是不允许创建新的结点结构，所以考虑其他方法。

在做二叉树相关的题时，一般都利用递归完成。本题中需要用一个指向当前链表最后结点的指针来完成，对于每个新输入的树，对左子树做递归操作，保证每次都更新指向当前链表最后结点的指针，那么当完成左子树时，当前根的前向指针（左指针）就指向其左子树链表的最后一个结点，同时去判断最后这个结点是否为空，若不为空，它的后向指针（右指针）就指向当前的根。接下来就更新这个最后结点的指针指向当前的根结点，再对右子树做同样操作。

参考了一篇博客，说得相对清晰，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);  
     }  
 }  

};