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

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

Q :给定一个二叉树，编写一个程序将其转换为双向链表。双向链表中的节点按照锯齿状层次顺序遍历形成的顺序排列

我的方法

我总是可以对树进行之字形级别顺序遍历并将其存储在数组中 然后创建一个双向链表。 但这个问题需要一个就地解决方案。 任何人都可以帮助解释应该使用递归方法吗？

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

#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;
    }