33.二叉搜索树与双向链表

题目：
把二叉搜索树转换成一个有序的双向链表，即左孩子指向上一个节点，右孩子指向下个节点，要求原地修改，不能创建新的链表。
思路：

• 二叉搜索树的中序遍历是一个有序数组
• 考察中序遍历中对根节点的操作

难点：

• 既然涉及到链表之间的穿针引线，那么肯定需要用到多个指针，指针的设计需要思路清晰
• 对遍历的概念要理解清晰，所谓遍历就是每个节点都会访问到，且只访问一次。
• 对第一个节点的处理

class Solution {
public:
    // 主方法
    TreeNode* Convert(TreeNode* root)
    {
        if(!root)
            return nullptr;
        getLink(root);
        return ret;
    }
   //中序遍历
    void getLink(TreeNode *root){
        if(!root)
            return ;
        getLink(root->left);
        //两个都为空，说明当前节点是中序遍历的第一个节点
        if(head==nullptr && ret==nullptr){
            head=root;
            ret=root;
        }
//不是第一个节点，那么root是当前访问的节点，head是root的上一个节点
        else{
            head->right=root;
            root->left=head;
            head=root;
        }
        getLink(root->right);
    }
    private:
    //head用来存放中序遍历过程中的上一个节点
    TreeNode *head=nullptr;
//ret用来存放根节点，作为返回结果
    TreeNode *ret=nullptr;
};