将二叉搜索树转换为双向链表

Question

最近的一次编码采访中提到了这个问题.

问:给定二叉树,编写程序将其转换为双向链表.双链表中的节点按照由Z字形级别顺序遍历形成的顺序排列

我的方法

我总是可以对树的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;
    }