Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree <code>[3,9,20,null,null,15,7]</code>,
<pre>
3
/
9 20
/
15 7
</pre>
return its zigzag level order traversal as:
<pre>
[
[3],
[20,9],
[15,7]
]
</pre>
Subscribe to see which companies asked this question

解题思路

这道题目一共有两个难点

• 将二叉树分层输出
• 每一层二叉树输出顺序不同

首先，我们考虑第一个难点。在学过数据结构之后，我们知道，将根节点放在一个队列中，然后进行扫描，不断地将他的节点放入队列，即可完成二叉树的层次遍历。
例如：
<pre>
1
/
2 3
/ /
4 5 7
</pre>
首先将根节点1放入队列

1

然后将根节点1的子节点放入队列

1 2 3

然后指针指向节点2，将节点的2的子节点放入队列

1 2 3 4

再指向节点3，将节点3的子节点放入队列

1 2 3 4 5 7

这样所有节点都被访问完毕，二叉树被分层遍历了

接着，我们考虑第二个难点。我们注意到，每两层之间遍历顺序不同，原先最开始输出的节点的子节点变成了最后输出的节点。于是我们自然而然地想到栈这种数据结构，满足先进后出的特点。再加一个变量来控制遍历顺序，就可以解决这一难点啦~

代码

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL) return res;
        int dir = 1;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        s1.push(root);
        while (true){
            vector<int> path;
            if (dir == 1){
                while (!s1.empty()){
                    TreeNode* one = s1.top();
                    s1.pop();
                    path.push_back(one->val);
                    if (one->left != NULL) s2.push(one->left);
                    if (one->right != NULL) s2.push(one->right);
                }
                res.push_back(path);
                if (s2.empty()) break;
                dir = 2;
            }else{
                while (!s2.empty()){
                    TreeNode* one = s2.top();
                    s2.pop();
                    path.push_back(one->val);
                    if (one->right != NULL) s1.push(one->right);
                    if (one->left != NULL) s1.push(one->left);
                }
                res.push_back(path);
                if (s1.empty()) break;
                dir = 1;
            }
        }
        return res;
    }
};