c - 将二进制搜索展平为有序的单链表 [C]

Question

我正在尝试将二叉搜索树展平为单链表。

二叉搜索树:

      6
    /   \
   4     8
  / \     \
 1  5     11
         / 
       10

扁平化单链表:

1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11

出于某种原因，我似乎无法弄清楚这一点。

我有一个树节点结构:

typedef stuct node {
    int key;
    struct node *left;
    struct node *right;
} Node;

我有一个函数可以为树节点创建和分配内存:

Node* newNode (int key) {
    Node *new = malloc (sizeof(Node));
    new->left = NULL;
    new->right = NULL;
    new->key = key;
    return new;
}

我有一个列表节点的结构:

typedef struct list {
    int key;
    struct list* next;
} List;

我有一个创建列表节点的函数:

List* newListNode (int key) {
    List *new = malloc(sizeof(List));
    new->key = key;
    new->next = NULL;
    return new;
}

我有创建二叉搜索树、插入值等的工作函数，但现在我需要创建一个函数来将树展平为列表。

List* flattenToLL(Node* root) {
    ...
}

我似乎无法弄清楚如何将其展平为单链表。我已经看到很多其他线程和站点讨论将二叉搜索树转换为双向或循环链表，但没有一个是关于将值复制到单链表中的。如果有人可以就我如何实现这一点提出建议，我将不胜感激。这是一个家庭作业，所以如果你也能提供一个小解释来帮助我学习那就太好了。

Answer 1

递归地做起来相对简单:

• 勾选左边的节点；如果那里有东西，将左边展平到列表 #1
• 勾选右边的节点；如果那里有东西，请将右边的内容展平到列表 #2
• 使用当前节点的键创建一个单节点列表#3
• 按照 #1 -> #3 -> #2 的顺序连接列表
• 返回连接列表作为结果

这里是你如何编写它:

List* flattenToLL(Node* root) {
    List *list1 = (root->left) ? flattenToLL(root->left) : NULL;
    List *list2 = (root->right) ? flattenToLL(root->right) : NULL;
    List *list3 = newNode(root->key);
    // The "middle" list3 cannot be NULL; append list2 to list3
    list3->next = list2; // If list2 is NULL, it's OK
    if (!list1) return list3; // Nothing to prepend
    List *last = list1;
    while (last->next) last=last->next; // Go to the end of list1
    last->next = list3; // Append list3+list2 to the end of list1
    return list1;
}