二叉搜索树与双向链表

class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(!pRootOfTree)
return nullptr;
TreeNode* lastNode = nullptr; //二叉树转化为双向链表之后的链表的最后一个结点
//因为还没有转化，所以现在还是指向空
//因为这个结点是是不断地更改的，所以递归的时候应该传递的是这个结点的地址
convertNode(pRootOfTree, &lastNode);//开始转换
//转换结束，lastNode指向的是链表的最后一个元素
while(lastNode!=nullptr && lastNode->left!= nullptr)
{
lastNode = lastNode->left;
}
return lastNode;
}
private:
//两个参数：
//1. pRootOfTree：当前树的根节点
//2. LastNode：当前树转换成链表后链表的最后一个元素的指针
void convertNode(TreeNode* pRoot, TreeNode** lastNode)
{
if(!pRoot)
return; //若根节点为空，则不对lastNode做改变

    if(pRoot->left) //若该树存在左子树，则求出左子树的最大的一个根节点
        convertNode(pRoot->left, lastNode);

    //连接左子树
    pRoot->left = *lastNode;
    if(*lastNode)
        (*lastNode)->right =pRoot;
    *lastNode = pRoot; //此时到结点pRoot为止最右边的结点就是pRoot

    //连接右子树
    if(pRoot->right)
        convertNode(pRoot->right, lastNode);
}

};