原题： 怎样从顶部开始逐层打印二叉树结点数据？
分析：逐层打印是个很明显的广度优先算法，BFS的首选自然是用队列保存没有被遍历过的节点，每一层查一个marker以区分不同的层，算法复杂度是每个节点被遍历一次，所以为O(n)，空间复杂度为某一层的最大节点数。为O(lg(n))。
原题： 怎样把二叉树按zig-zag的顺序转换为一个链表？
分析：这个是类似的，不过就用栈了，计算复杂度为O(n)，空间复杂度为O(log(n))。
void printTreeByLevel(BinaryTreeNode * root)
{
stack<BinaryTreeNode *> nodes_0;
stack<BinaryTreeNode *> nodes_1;
if(root == NULL)
return ;
nodes_0.push(root);
stack<BinaryTreeNode *> * currentLevelNodes = &nodes_0;
stack<BinaryTreeNode *> * nextLevelNodes = &nodes_1;
while(currentLevelNodes->size()> 0)
{
BinaryTreeNode * t = currentLevelNodes->top();
currentLevelNodes->pop();
cout<<t->value<<endl;
if(currentLevelNodes == &nodes_0)
{
if(t->right !=NULL)
{
nextLevelNodes->push(t->right);
}
if(t->left !=NULL)
{
nextLevelNodes->push(t->left);
}
}
else
{
if(t->left !=NULL)
{
nextLevelNodes->push(t->left);
}
if(t->right !=NULL)
{
nextLevelNodes->push(t->right);
}
}
if( currentLevelNodes->size() == 0)
swap(currentLevelNodes ,nextLevelNodes );
}
}
{
stack<BinaryTreeNode *> nodes_0;
stack<BinaryTreeNode *> nodes_1;
if(root == NULL)
return ;
nodes_0.push(root);
stack<BinaryTreeNode *> * currentLevelNodes = &nodes_0;
stack<BinaryTreeNode *> * nextLevelNodes = &nodes_1;
while(currentLevelNodes->size()> 0)
{
BinaryTreeNode * t = currentLevelNodes->top();
currentLevelNodes->pop();
cout<<t->value<<endl;
if(currentLevelNodes == &nodes_0)
{
if(t->right !=NULL)
{
nextLevelNodes->push(t->right);
}
if(t->left !=NULL)
{
nextLevelNodes->push(t->left);
}
}
else
{
if(t->left !=NULL)
{
nextLevelNodes->push(t->left);
}
if(t->right !=NULL)
{
nextLevelNodes->push(t->right);
}
}
if( currentLevelNodes->size() == 0)
swap(currentLevelNodes ,nextLevelNodes );
}
}