103. 二叉树的锯齿形层序遍历

Introduction

Question：103. 二叉树的锯齿形层序遍历

Analysis

虽然直接层次遍历获得层次遍历的结果，然后在返回前处理成锯齿型也行（这样实现比较简单），但是访问元素的顺序确实正常的层次遍历，而不是锯齿形的层次遍历。不过这道题要返回的是最终结果，所以这样做也没啥问题。

一开始看到这个问题，想着是用一个队列来做，用层次遍历的方式遍历整课树，但是在将子树压入队列时在奇数层先压右子树，但是后来发现这样做是有问题的，虽然默认的测例可以过，但是对于下面这个例子就不能解决了：

      1
   /     \
  2       3
 / \     /  \
4    5   6   7

这里我们以上面的树为例子，简单探索一下，锯齿形层次遍历的规律：

访问第一层时，访问顺序是[1]，这时保存指针的顺序可以为[2, 3]（先左后右），也可是是[3, 2]（先右后左）。

访问第二层时，访问顺序是[3, 2]，保存指针的顺序可以是[6,7,4,5]（先左后右），也可以是[7, 6, 5, 4]（先右后左）。

从第二层看的话，奇数层先左后右，偶数层先右后左的访问方式才是正确的，但是也需要修正，即保存指针的顺序与下一层的访问顺序是倒过来的。既然是倒过来的，我们就可以使用栈来保存了。同时因为要边保存子树的指针，又要访问当前层的节点，所以我们需要两个栈交替实现。

Implement

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (root == nullptr) return res;

    stack<TreeNode*> st1;
    stack<TreeNode*> st2;
    st1.push(root);
    vector<int> vec;
    bool flag = false;
    while(!st1.empty()) {

        for(int i = 0, size = st1.size();i < size;i++) {
            root = st1.top(); st1.pop();
            vec.push_back(root->val);
            if (flag) swap(root->left, root->right);
            if (root->left) st2.push(root->left);
            if (root->right) st2.push(root->right);
        }
        if (!vec.empty()) res.push_back(vec);
        vec.clear();
        swap(st1, st2);
        flag = !flag;
    }
    return res;
}