二叉搜索树到双链表的转换

Question

这个问题是在最近的一次编码采访中被问到的。

问：给定一个二叉树，写一个程序把它转换成双链表。双链表中的节点按zig-zag级顺序遍历形成的序列排列

Answer 1

这是递归方法。注意，这里root将指向所形成的列表中的一些inbetween元素。所以，只需从根向后遍历就可以得到头部。

#define NODEPTR struct node*

NODEPTR convert_to_ll(NODEPTR root){
    if(root->left == NULL && root->right == NULL)
        return root;
    NODEPTR temp = NULL;
    if(root->left != NULL){
        temp = convert_to_ll(root->left);
        while(temp->right != NULL)
            temp = temp->right;
        temp->right = root;
        root->left = temp;
    }
    if(root->right != NULL){
        temp = convert_to_ll(root->right);
        while(temp->left != NULL)
            temp = temp->left;
        temp->left = root;
        root->right = temp;
    }
    return root;
    }