BTLevelOrder-SeparateLevel
今天偶然看到师弟站站大神的博客，题目本是求BT的高度，但是他用层序遍历的方法，突然发现这种代码之前好像都不是这么写的，于是有种发现新大陆的感觉。
主要是之前知道层序遍历，但是区分层的时候，要么是编程之美vector cur last来控制，借助的数据结构不那么make sense，要么miloyip的两个队列交换来记录每层的遍历，
总觉得这么一个功能还要用牛刀，于是终于看到用一个queue来实现，思路和编程之美一样，只需要添加每层遍历之前记录当前的queue大小的遍历就可以了，保证这一层访问到这里
一定结束了，但是不需要额外的cur last来记录，好的算法应该这样，这些细节是封装在DS里面的。
附上记录层序遍历结果的代码，以后层序遍历如果区分层就用这个了。注意里面有一点注意，就是for可能一个都没有，此时onelevel空，后面push到总结果要过滤掉空vector的情况。
vector<vector<int> > levelOrder(TreeNode *root) {
vector<int> onelevel;
vector<vector<int> > alllevel;
if(root==NULL) return alllevel;
queue<TreeNode*> Q;
Q.push(root);
TreeNode* p;
onelevel.push_back(root->val);
alllevel.push_back(onelevel);
while(!Q.empty())
{
int size=Q.size();
onelevel.clear();
for(int i=0;i<size;i++)
{
p=Q.front();
Q.pop();
if(p->left!=NULL)
Q.push(p->left), onelevel.push_back(p->left->val);
if(p->right!=NULL)
Q.push(p->right), onelevel.push_back(p->right->val);
}
if(onelevel.size()!=0)
alllevel.push_back(onelevel);
}
return alllevel;
}
我之前也没想到这么简洁的层序遍历，mileyip博客里几个代码似乎也没有这么简洁的，编程之美团队也没想到么，虽然vector思路一样，但是queue的更好。
附上友情链接：
http://www.chengzhanzhan.cn/leetcode-2/maximum-depth-of-binary-tree/#comment-8 师弟的博客，强推
http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html mileyip的，还上了编程之美
http://blog.csdn.net/richardzrc/article/details/27677067 鄙人之前总结的，以后都会用上述的算法代替了，除非还有特殊需求。
: )
另外用这个简洁的算法连了下差不多的题，发现自己急于提交，很多细节都没考虑全，这个如果在面试一定会被扣分的，千万不要急着说完成了，一定要考虑全，不要怕时间长。
每次遍历之后奇偶层的bool变量都要反转的 ，然后每次遍历前onelevel都clear的，然后记得把第一层root push进去, 然后后面
如果onelevel可能为空的需要过滤一下。再考虑root空，从这样一个代码都是需要各方面都考虑全面的，如果onelevel为空了，
说明也是遍历到最后一层了，后面就结束了。
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int> >alllevel;
vector<int> onelevel;
if(root==NULL)
return alllevel;
queue<TreeNode*> Q;
Q.push(root);
onelevel.push_back(root->val);
alllevel.push_back(onelevel);
TreeNode*p;
bool evenlevel=true;
while(!Q.empty())
{
int size=Q.size();
onelevel.clear();
for(int i=0;i<size;i++)
{
p=Q.front();
Q.pop();
if(p->left!=NULL)
Q.push(p->left), onelevel.push_back(p->left->val);
if(p->right!=NULL)
Q.push(p->right), onelevel.push_back(p->right->val);
}
if(onelevel.size()!=0)
{
if(evenlevel)
reverse(onelevel.begin(),onelevel.end());
evenlevel=!evenlevel;
alllevel.push_back(onelevel);
}
}
return alllevel;
}