Given a binary tree, design an algorithm which creates alinked list of all the nodes at each depth (e.g., if you have a tree with depthD, you’ll have D linked lists).

CareerCup4.4.cpp

#include <iostream>
#include <vector>
#include <list>

struct Node
{
  	int data;
	Node* leftchild;
	Node* rightchild;
	Node()
	{
		leftchild=NULL;
		rightchild=NULL;
	}
};
Node* MakeSearchTree(int*, int*);
void GenerateLists(std::vector<std::list<int> >&, Node*,int);

int main()
{
	int a[10] = {1,2,3,4,5,6,7,8,9,10};
	Node *root = MakeSearchTree(&a[0],&a[9]);
	std::vector<std::list<int> > vec;
	GenerateLists(vec,root,0);
	for(int i=0;i<vec.size();i++)
	{
		for(std::list<int>::iterator iter = vec[i].begin();iter!=vec[i].end(); iter++)
		{
			std::cout<<*iter<<" ";
		}
		std::cout<<std::endl;
	}
}

void GenerateLists(std::vector<std::list<int> > &lists, Node* node,int layer)
{
	if(lists.size()<=layer)
	{
		std::list<int> list;
		lists.push_back(list);
		lists[layer].push_back(node->data);
	}
	else
	{
		lists[layer].push_back(node->data);
	}
	if(node->leftchild!=NULL)
	{
		GenerateLists(lists, node->leftchild, layer+1);
	}
	if(node->rightchild!=NULL)
	{
		GenerateLists(lists, node->rightchild, layer+1);
	}
}

Node* MakeSearchTree(int* begin, int* end)
{
	if(begin==end)
	{
		Node* node = new Node();
		node->data = *begin;
		return node;
	}
	if(begin<end)
	{
		int* mid = begin + (end-begin)/2;
		Node* node = new Node();
		node->data = *mid;
		if((mid-1)>=begin)
		{
			node->leftchild = MakeSearchTree(begin,mid-1);
		}
		if((mid+1)<=end)
		{
			node->rightchild = MakeSearchTree(mid+1,end);
		}
		return node;
	}
	
}