题意：
        输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
        

方法一：
直接模拟+链表

思路：
        二叉搜索树的中序遍历是有序的。
        因此，我们对二叉搜索树中序遍历，并将结果存入一个双向链表中。


class Solution {
public:
    TreeNode *head,*p;//新建双向链表
    int i=0;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree==nullptr){
            i++;
            return nullptr;
        }
        
        Convert(pRootOfTree->left);//递归左儿子
        if(i==1){//当遍历到最左下角时，则是链表的第一个节点
            head=pRootOfTree;
            p=pRootOfTree;
            
        }else{//否则，拼接链表的其他节点
            p->right=pRootOfTree;
            pRootOfTree->left=p;
            p=p->right;
        }
        
        Convert(pRootOfTree->right);//递归右儿子
        return head;
    }
};

时间复杂度：
空间复杂度：

方法二：
直接模拟+空间优化

思路：
        利用中序遍历和一个指针实现。
        指针 p 是（中序遍历序列中）当前节点 root 的上一个节点，通过这两个节点的连接，即可实现树的原地修改。
    
        最后 指针p 会指向中序遍历序列的最后一个节点。
        然后通过 指针p 的循环前移操作 ，便可得到双向链表的首节点。 



class Solution {
public:
    TreeNode* p=nullptr;//中序遍历序列中的上一个节点
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree==nullptr)
            return nullptr;
        f(pRootOfTree);
        while(p->left){//链表指针从后往前遍历，找到第一个节点
            p=p->left;
        }
        return p;
    }
    void f(TreeNode* root){
        if(root==nullptr)
            return;
        f(root->left);//递归左儿子
        root->left=p;
        if(p)//如果p非空，则指针p的右指针 指向root
            p->right=root;
        
        p=root;
        f(root->right);//递归右儿子
    }
};

时间复杂度：
空间复杂度：