lintcode二叉树的锯齿形层次遍历 （双端队列）

题目链接：

　　http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/

二叉树的锯齿形层次遍历

　　给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）

样例

　　给出一棵二叉树 {3,9,20,#,#,15,7},

   　　 3

 　　  / \

　　  9  20

　　    /  \

 　　  15   7

　　返回其锯齿形的层次遍历为：

　　[

 　　 [3],

 　　 [20,9],

　　  [15,7]

　　]

思路：

　　我们用双端队列模拟一下这个过程：开始的时候是正向遍历，3通过push_front()放入队列Q， 形成Q[3]。接着我们规定正向遍历的时候从队列前端去元素，下一层元素放入队列的时候是放入队列的后端；而反向遍历的时候正好相反，唯一不同的就是反向遍历时，下一层的右孩子结点（如果有）先放入队列的前端。

　　开始Q[3](从前端取数字), 然后下一层放入后是Q[9,20](从后端去数字)，20的下一层放入后是Q[15,7,9], 然后变成Q[15,7](从前端去数字)，最后得到遍历的结果。

代码实现：

/**

 * 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 = ;//上一层的节点数目

        int curLevelCnt = ;//下一层节点数目

        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 == ){//这一层完毕

                vv.push_back(v);

                v.clear();

                levelCnt = curLevelCnt;

                curLevelCnt = ;

                dir = !dir;

            }

        }

        return vv;

    }

};

lintcode二叉树的锯齿形层次遍历 （双端队列）的相关教程结束。