题解 | #二叉搜索树与双向链表#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

/**
 *
 * @param pRootOfTree TreeNode类
 * @return TreeNode类
 */

static struct TreeNode* pre =NULL;
//中序遍历
void mid(struct TreeNode* p ){
    if(!p){ //出口条件，节点为空
        return ;
    }
    mid(p->left);//遍历左结点
   
    p->left=pre;//前驱节点设为pre;
    if(pre!=NULL)
        pre->right=p;//后继节点设为p; !!!注意pre是一个指针，它指向p前面的那个节点
    pre=p;   
    mid(p->right);//遍历右结点
    
}
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    // write code here
    //struct TreeNode* pre = NULL;
    if (pRootOfTree != NULL) {
        mid(pRootOfTree);//中序遍历
        pre->right = NULL;//将最后一个节点的后继记为空
    }
    if (pRootOfTree)//判断节点非空
        while (pRootOfTree->left != NULL) {//一直遍历左结点直到为空
            pRootOfTree = pRootOfTree->left;
        }
    return pRootOfTree;//返回中序遍历的一个节点指针
}