Flatten binary search to in order singly linked li

问题:

I am trying to flatten a binary search tree to a singly linked list.

Binary search tree:

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

Flattened Singly Linked List:

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

I can't seem to figure this out for some reason.

I have a struct for the tree nodes:

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

I have a function to create and allocate memory to the tree node:

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

I have a struct for the list nodes:

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

I have a function to create the list node:

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

And I have working functions to create the binary search tree, to insert the values, etc., but now I need to create a function to flatten the tree to a list.

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

I just can't seem to figure out how to flatten it to a singly linked list. I have seen a lot of other threads and sites discussing a conversion of a binary search tree to a doubly or circular linked list, but none about copying the values into a singly linked list. If anyone can offer up suggestions on how I can accomplish this I would really appreciate it. This is for a homework assignment, so if you can also provide a small explanation to help me learn that would be great.

回答1:

This is relatively simple to do recursively:

• Check the node on the left; if there is something there, flatten the left to a list #1
• Check the node on the right; if there is something there, flatten the right to a list #2
• Create a single-node list #3 with the key of the current node
• Concatenate the lists in the order #1 -> #3 -> #2
• Return the concatenated list as your result

Here is how you can code it up:

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

回答2:

You need to do an in-order traversal, adding each element in turn to the list.

The pseudo-code for this is:

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.

That's it, as simple as it gets. Step 1, process the left subtree. Step 2, add the data. Step 3, process the right subtree.

The only "clever" bit is correct handling of empty subtrees in a way that makes the code succinct.

---

Keep in mind that, for maximum efficiency, appending to a linked list may be a relatively expensive operation if the pointer to the final element (tail) is not cached somewhere. That will entail having to find the tail for each element being added, something that will turn your flattening algorithm into an O(n2) one.

Since inserting an element at the start of a linked list is almost invariably O(1) by virtue of the fact you must maintain a head pointer, it's often more efficient to do a reverse in-order traversal instead:

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.

This keeps the flattening operation at O(n).

回答3:

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

回答4:

Below is the Java code if someone is interested:

public static Node bTreeToLinkedList(TreeNode root) {
    Node list1 = root.getLeftChild() != null ? bTreeToLinkedList(root.getLeftChild()) : null;
    Node list2 = root.getRightChild() != null ? bTreeToLinkedList(root.getRightChild()) : null;
    Node list3 = ll.new Node((int) root.getData());

    list3.setNext(list2);
    if (list1 == null)
        return list3;

    Node last = list1;
    while (last.getNext() != null)
        last = last.getNext();
    last.setNext(list3);

    return list1;
}

回答5:

We can use recurssion where we build a linked list for each level in the tree and add the list to a vector of lists. With this solution we need to keep a track of which level we are on, so if we have a linked list already for a level and we visit a node on a level visited before we can just add to that list.

I have not added any code for my own node class as its not relevant to the question, also no memory clean up is being demonstrated, however a better solution would be to use boost::shared_ptr to handle clean up.

void generateLists(vector<list<node*>* >*& lists, node* root, int level)
{
    //base case
    if(root == NULL)
        return;

    //if we have don't have a linked list at this level so create this
    if((int)lists->size() == level)
    {
        list<node*>* ls = new list<node*>();
        ls->push_back(root);
        lists->push_back(ls);
    }
    else
    {
        //re-use existing list
        list<node*>* ls = lists->at(level);
        if(ls != NULL)
            ls->push_back(root);
    }

    //in order traversal
    generateLists(lists, root->left, level+1);
    generateLists(lists, root->right, level+1);
}

int main(void)
{
    //create a test binary tree
    node root(6);
    node n2(3);
    node n3(9);
    node n4(2);
    node n5(5);
    node n6(8);
    node n7(9);

    root.left = &n2;
    root.right = &n3;
    n2.left = &n4;
    n2.right=&n5;
    n3.left=&n6;
    n3.right=&n7;

    //will hold a vector of lists for each level in the tree
    vector<list<node*>* >* lists = new vector<list<node*>* >();
    int level=0;
    generateLists(lists, &root, level);
    vector<list<node*>* >::iterator it;

    //convert each level in the tree to a single linked list
    list<node*> flattened;
    for(it = lists->begin(); it != lists->end(); it++)
    {
        list<node*>* linkedList = (*it);
        list<node*>::iterator itNode;
        for(itNode = linkedList->begin(); itNode != linkedList->end(); itNode++)
            flattened.push_back(*itNode);
    }

    //output the tree as a linked list
    list<node*>::iterator itNode;
    for(itNode = flattened.begin(); itNode != flattened.end(); itNode++)
        cerr<<(*itNode)->val<<" ";
}

回答6:

There is also non-recursive solution for the problem here.

It gives you O(n) time complexity and O(1) space complexity. With recursive solution you can get stack overflow if e.g. you apply it to its own output for a big node set.

回答7:

 private static BSTNode head;
 private static BSTNode tail;
 public static void inorderTraversal(BSTNode node) {
        if(node.left != null) {
            inorderTraversal(node.left);
        }
        System.out.print(node.data + " ");
        constructLinkedList(node.data);
        if(node.right != null) {
            inorderTraversal(node.right);
        }
    }

public static void constructLinkedList(int data) {
        if(head == null) {
            head = new BSTNode(data);
            head.left = null;
            tail = head;
        } else {
            BSTNode node = new BSTNode(data);
            tail.right = node;
            tail.left = null;
            tail = node;
        }
   }

   public static void linkedListToString() {
        BSTNode curr = head;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while(curr.right != null) {
            sb.append(curr.data).append("->");
            curr = curr.right;
        }
        if(curr.right == null)
            sb.append(curr.data).append("->NULL");
        sb.append("]");
        System.out.print(sb.toString());

   }