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 = 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;
    }
};