题目链接：Binary Tree Zigzag Level Order Traversal

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 {3,9,20,#,#,15,7},

    3 
   / \ 
  9  20 
    /  \ 
   15   7

return its zigzag level order traversal as:

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

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1 
  / \ 
 2   3 
    / 
   4 
    \ 
     5

The above binary tree is serialized as “{1,2,3,#,#,4,#,#,5}”.

这道题的要求是Zigzag方式遍历二叉树，即分层遍历，先是从左到右，接着从右到左，然后从左到右，接着从右到左，以此类推。

和Binary Tree Level Order Traversal类似，由于需要把每层的节点分别放入到数组中，因此需要引入变量n记录每层的节点数量。然而由于需要按Zigzag方式遍历，因此在偶数层需要反转即可（假设根节点为第12层）。再剩下的，就是广度优先遍历的方法了。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution
{
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int> > vvi;
        
        if(root == NULL)
            return vvi;
        
        queue<TreeNode *> q;
        q.push(root);
        bool zigzag = false;
        while(!q.empty())
        {
            vector<int> vi;
            for(int i = 0, n = q.size(); i < n; ++ i)
            {
                TreeNode *temp = q.front();
                q.pop();
                if(temp -> left != NULL)
                    q.push(temp -> left);
                if(temp -> right != NULL)
                    q.push(temp -> right);
                vi.push_back(temp -> val);
            }
            if(zigzag)
                reverse(vi.begin(), vi.end());
            vvi.push_back(vi);
            zigzag = !zigzag;
        }
        
        return vvi;
    }
};