[leetcode-103-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,null,null,15,7],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

思路：

和层序遍历差不多，leetcode-102-Binary Tree Level Order Traversal，唯一不一样的就是判断是否为偶数层，

如果为偶数层则需要将该层翻转过来。

vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> result;
        if (root == NULL)return result;
        queue<TreeNode*>que;
        que.push(root);
        bool flag = false;//判断是否需要翻转
        while (!que.empty())
        {
            int size = que.size();            
            vector<int>level;
            for (int i = 0; i < size;i++)
            {
                TreeNode* temp = que.front();
                que.pop();
                if (temp->left != NULL)que.push(temp->left);
                if (temp->right != NULL)que.push(temp->right);
                level.push_back(temp->val);                
            }
            if (flag)
            {
                reverse(level.begin(), level.end());
                flag = !flag;
            }
            else flag = !flag;
            
            result.push_back(level);        
        }
        return result;
    }