程序员代码面试指南 2.15：将搜索二叉树转换成双向链表

1、思路

• 按照二叉树的中序遍历顺序，将每个节点放入队列q中；

• 从q中依次弹出节点，并按照弹出的顺序重新连接所有节点即可。

2、代码

double_list_node * convert(BST * root)
{
    queue<BST*> q;
    inOrderTreeToQueue(root, q);

    root = q.front();
    q.pop();

    // head 为双链表头结点
    double_list_node *head = new double_list_node(), *pre = head;
    pre->val = root->val;
    pre->pre = nullptr;     //头结点往前为空

    while (!q.empty())
    {
        double_list_node *cur = new double_list_node();
        BST *tmp = q.front();
        q.pop();
        cur->val = tmp->val;

        pre->next = cur;    //连接前一节点和当前节点
        cur->pre = pre;

        pre = cur;          //指针后移
    }

    pre->next = nullptr;    //尾结点往后为空
    return head;
}