v题目链接：
http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/
v二叉树的锯齿形层次遍历
给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
v样例
给出一棵二叉树 {3,9,20,#,#,15,7},
3 / \ 9 20 / \ 15 7
返回其锯齿形的层次遍历为：
[ [3], [20,9], [15,7] ]
v思路：
我们用双端队列模拟一下这个过程：开始的时候是正向遍历，3通过push_front()放入队列Q， 形成Q[3]。接着我们规定正向遍历的时候从队列前端去元素，下一层元素放入队列的时候是放入队列的后端；而反向遍历的时候正好相反，唯一不同的就是反向遍历时，下一层的右孩子结点（如果有）先放入队列的前端。
开始Q[3](从前端取数字), 然后下一层放入后是Q[9,20](从后端去数字)，20的下一层放入后是Q[15,7,9], 然后变成Q[15,7](从前端去数字)，最后得到遍历的结果。
v代码实现：
/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { /** * @param root: The root of binary tree. * @return: A list of lists of integer include * the zigzag level order traversal of its nodes' values */ public: vector<vector<int>> zigzagLevelOrder(TreeNode *root) { // write your code here vector<vector<int>> vv; if(root == NULL) return vv; deque<TreeNode *> q; q.push_back(root); bool dir = true;//true表示从左向右存储层次遍历，否则是从右向左 int levelCnt = 1;//上一层的节点数目 int curLevelCnt = 0;//下一层节点数目 vector<int> v; while(!q.empty()){ TreeNode *cur; if(dir){ cur = q.front(); q.pop_front(); } else { cur = q.back(); q.pop_back(); } if(dir){ if(cur->left){ q.push_back(cur->left); ++curLevelCnt; } if(cur->right){ q.push_back(cur->right); ++curLevelCnt; } } else { if(cur->right){ q.push_front(cur->right); ++curLevelCnt; } if(cur->left){ q.push_front(cur->left); ++curLevelCnt; } } v.push_back(cur->val); --levelCnt; if(levelCnt == 0){//这一层完毕 vv.push_back(v); v.clear(); levelCnt = curLevelCnt; curLevelCnt = 0; dir = !dir; } } return vv; } };
