扁平化二分搜索到有序单链表[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

Why dont you do inorder traversal and add values to list in a way.  

public List<Integer> inorderToList(TreeNode<Integer> node, List<Integer> list) {
        if(node == null) {
            return list;
        } 
        if (node != null) {
            list = inorderToList(node.getLeft(), list);
            list.add(node.getValue());
            list = inorderToList(node.getRight(), list);
        }
        return list;
    }

Answer 2

您需要按顺序遍历，将每个元素依次添加到列表中。

这方面的伪代码是：

def traverse (node, list):
    if node == NULL: return       # Ignore empty subtrees.
    traverse (node.left, list)    # Do left subtree first.
    list.append (node.data)       # Then current node.
    traverse (node.right, list)   # Then right subtree.

list = new List()                 # Create empty list.
traverse (root, list)             # Collapse tree to list.

就这样，尽可能简单。第1步，处理左侧子树。第2步，添加数据。第3步，处理右侧子树。

唯一“聪明”的地方是以一种简洁的方式正确处理空子树。

请记住，为了获得最大效率，如果指向最终元素（tail）的指针没有缓存在某个地方，那么将其附加到链表可能是一个相对昂贵的操作。这将需要为添加的每个元素找到尾部，这将把你的展平算法变成一个O（n2）1。

由于在链表的开头插入一个元素几乎总是O（1），因为您必须维护一个head指针，所以通常更有效的方法是反向遍历：

def traverse (node, list):
    if node == NULL: return       # Ignore empty subtrees.
    traverse (node.right, list)   # Do right subtree first.
    list.insert (node.data)       # Then current node at list start.
    traverse (node.left, list)    # Then left subtree.

这将扁平化操作保持在O（n）。

Answer 3

这是相对简单的递归操作：

• 检查左侧的节点；如果有什么，请将左侧展平为列表#1

以下是如何编写代码：

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