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

二叉搜索树中序遍历即是升序，所以我们使用队列，中序遍历把结点存入队列中，再出队，把结点链接起来即可

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pRootOfTree TreeNode类 
 * @return TreeNode类
 */
 
 //中序遍历
void LDR(struct TreeNode* T, struct TreeNode* queue[1001],int* tail){
    if(T==NULL){
        return;
    }
    
    LDR(T->left,queue,tail);
    queue[(*tail)++]=T;   //中序遍历，将结点指针放入队中
    LDR(T->right,queue,tail);
    
}

struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    // write code here
    if(pRootOfTree==NULL){
        return NULL;
    }
    
    int queue_head=0;
    int queue_tail=0;
    struct TreeNode* queue[1001];//使用数组实现队列功能，数组中存放的是结点指针
    
    LDR(pRootOfTree,queue,&queue_tail);//中序遍历，把所有结点入队
    
    queue[queue_tail]=NULL;//二叉树所有结点入队后，把最后一个结点之后一个队列位置赋NULL值，因为初始化是随机值，
                           //而链表最后一个结点下一个指针要指向NULL才行
    
    //初始化需要的前结点，当前节点，下一个结点
    struct TreeNode* pre=NULL;
    struct TreeNode* cur=queue[queue_head++]; //出队第一个
    struct TreeNode* list_head=cur;//函数需要返回值，我们就返回队列第一个结点，即中序遍历第一个结点即可
    struct TreeNode* next=queue[queue_head];
    //将结点之间连接起来，构成链表
    while(queue_head<=queue_tail){
        cur->left=pre;
        cur->right=next;
        pre=cur;
        cur=next;
        queue_head++;//队头向后移动
        next=queue[queue_head];//出队下一个
    }
    
    return list_head;
}