题解 | #将搜索二叉树转换成双向链表#

思路：中序遍历，使用栈记录非递归实现。维护遍历二叉树的前一个节点生成的链表节点，每次将二叉树当前遍历节点生成的链表节点与维护的前一个相互连接即可。

# include <bits/stdc++.h>
using namespace std;

struct double_list_node{
    int val;
    struct double_list_node * pre, * next;
};

struct BST{
    int val;
    struct BST * lch, * rch;
};

BST * input_BST()
{
    int n, fa, lch, rch;
    scanf("%d", &n);
    BST * root, * new_node;
    map<int, BST *> mp;
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d %d", &fa, &lch, &rch);
        if (mp.find(fa) == mp.end()) {
            new_node = (BST *)malloc(sizeof(BST));
            mp[fa] = new_node;
            new_node->val = fa;
            if (i == 1) root = new_node;
        }
        if (lch && mp.find(lch) == mp.end()) {
            new_node = (BST *)malloc(sizeof(BST));
            mp[lch] = new_node;
            new_node->val = lch; new_node->lch = new_node->rch = NULL;
        }
        if (rch && mp.find(rch) == mp.end()) {
            new_node = (BST *)malloc(sizeof(BST));
            mp[rch] = new_node;
            new_node->val = rch; new_node->lch = new_node->rch = NULL;
        }
        mp[fa]->lch = (lch ? mp[lch] : NULL);
        mp[fa]->rch = (rch ? mp[rch] : NULL);
    }
    return root;
}


double_list_node * convert(BST * root)
{
    //////在下面完成代码
    double_list_node * head, * pre=nullptr;
    stack<BST*> s;
    BST * temp=root;
    double_list_node * lnode;
    while(!s.empty()||temp){
        while(temp){
            s.push(temp);
            temp=temp->lch;
        }
        temp=s.top();
        s.pop();
        lnode=new double_list_node();
        lnode->val=temp->val;
        if(pre==nullptr){
            head=lnode;
            pre=lnode;
        }
        else{
            lnode->pre=pre;
            pre->next=lnode;
            pre=lnode;
        }
        temp=temp->rch;
    }
    return head;
}

void print_double_list(double_list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    BST * root = input_BST();
    double_list_node * new_double_head = convert(root);
    print_double_list(new_double_head);
    return 0;
}