4-4.cpp

// Time complexity O(n). Space complexity O(n)

#include "stdafx.h"
#include "iostream"
#include "vector"
using namespace std;


const int MAXINT = 0x7fffffff;

template<typename T>
class TreeNode
{
public:
	T data;
	TreeNode *left, *right;     
	TreeNode() { left = right = NULL; }
	TreeNode(T t): data(t), left(NULL), right(NULL){}
};

template<typename T>
class Tree
{
private:
	TreeNode<T> *root, *pFlag;
public:
	Tree() { root = NULL; }
	Tree(TreeNode<T> *t): root(t){}

	TreeNode<T>* GetRoot(){ return root; }

	void SetPFlag(TreeNode<T> *pt)
	{
		pFlag = pt;
	}

	// tArr is in ascending order
	// the result is a binary search tree	
	TreeNode<T>* InitializeTree(T *tArr, int low, int high, TreeNode<T> *pnode)
	{
		if(low > high || tArr == NULL)
			return NULL;
				
		int mid = low + (high - low) / 2;
		pnode = new TreeNode<T>(tArr[mid]);

		// Initialize left
		pnode->left = InitializeTree(tArr, low, mid - 1, pnode->left);
		// Initialize right
		pnode->right = InitializeTree(tArr, mid + 1, high, pnode->right);

		return pnode;
	}

	void PrintPre(TreeNode<T> *pnode)
	{
		if(pnode == NULL)
			return;

		cout << pnode->data << " ";
		PrintPre(pnode->left);
		PrintPre(pnode->right);		
	}

	vector<vector<TreeNode<T>*>> GetDepLists()
	{
		vector<vector<TreeNode<T>*>> vTNode;
		vector<T>::size_type curdep = 0;		
		vector<TreeNode<T>*> queue, vCur;
		queue.push_back(root);
		queue.push_back(pFlag);
		vTNode.push_back(vCur);

		while(!queue.empty())
		{
			// dequeue
			TreeNode<T> *pNode = queue.front();
			queue.erase(queue.begin());

			if(pNode->left != NULL)
				queue.push_back(pNode->left);
			if(pNode->right != NULL)
				queue.push_back(pNode->right);

			// meet end of the level
			if(pNode == pFlag)
			{				
				curdep++;
				if(!queue.empty()){
					queue.push_back(pFlag);
					vector<TreeNode<T>*> vCur;
					vTNode.push_back(vCur);
				}
			}
			else			
				vTNode[curdep].push_back(pNode);
			
		}

		return vTNode;
	}

	void PrintDepList(vector<vector<TreeNode<T>*>> vvDepList)
	{
		for(int i = 0; i < vvDepList.size(); i++)
		{
			for(int j = 0; j < vvDepList[i].size(); j++)
				cout << vvDepList[i][j]->data << " ";
			cout << endl;
		}
		cout << endl;
	}
};

int main()
{
	int iArr[] = {1, 2, 5, 7, 10, 13, 15, 21, 22};
	int low = 0, high = sizeof(iArr) / sizeof(int) - 1;

	Tree<int> *ptree = new Tree<int>();
	TreeNode<int> *proot = ptree->InitializeTree(iArr, low, high, ptree->GetRoot());
	ptree = new Tree<int>(proot);

	// make a flag
	TreeNode<int> *pFlag = new TreeNode<int>(MAXINT);
	ptree->SetPFlag(pFlag);

	vector<vector<TreeNode<int>*>> vvDepList = ptree->GetDepLists();
	ptree->PrintDepList(vvDepList);

	system("pause");
	return 0;
}