103二叉树的锯齿形层次遍历

题目链接

题目描述：

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

实例：
例如：
给定二叉树 [3,9,20,null,null,15,7]

返回锯齿形层次遍历如下：

[
[3],
[20,9],
[15,7]
]

解题思路

  本题要求在常规的队列+BFS基础上进行“之字形”遍历。说明我们要对BFS的过程做出一些调整。
  我们观察发现，假设从第0层开始算起，偶数层输出顺序从左到右，而奇数层输出顺序从右到左。通常来说，我们一般习惯的输出顺序为从左到右，所以只需要一个队列利用其先进先出的特性即可完成需求。现在，我们可能会想念栈，因为栈的特点是先进后出，符合奇数层输出顺序。
  这时，我们需要引入c++ STL库中的一个容器——deque，也就是我们熟悉的双端队列。它可以同时实现先进先出和先进后出两个特点。也就是说从左到右，我们可以push_back()，即常规地从队尾进队；也可以push_front()，即从队头进队。

代码

cpp

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(!root)
            return result;
        queue<TreeNode*> queue_Tree;
        queue_Tree.push(root);
        int height = 0;    //从第0层开始算起
        while(!queue_Tree.empty()){
            int n = queue_Tree.size(); //获取每一层的结点数
            deque<int> deque_Tree;     //双端队列
            for(int i = 0; i < n; i++){
                TreeNode* node = queue_Tree.front();
                queue_Tree.pop();
                if(height % 2 == 0)  //偶数层，从左到右
                    deque_Tree.push_back(node->val);
                else                 //奇数层，从右到左
                    deque_Tree.push_front(node->val);
                
                if(node->left)
                    queue_Tree.push(node->left);
                if(node->right)
                    queue_Tree.push(node->right);
            }
            height++;
            result.push_back( vector<int>( deque_Tree.begin(), deque_Tree.end() ) );
        }
        return result;
    }
};

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。