Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal Show result 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).

http://www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/

Discussion

level order traversal的时候记下是哪一层，偶数层reverse就可以了。

Solution

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: A list of lists of integer include 
     *          the zigzag level order traversal of its nodes' values 
     */
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> result;
        if(root == NULL) return result;
        queue<TreeNode*> nodes;
        int level = 0;
        nodes.emplace(root);
        while(nodes.empty() == false) {
            int size = nodes.size();
            vector<int> cur_level;
            for(int i=0; i<size; i++) {
                cur_level.emplace_back(nodes.front()->val);
                if(nodes.front()->left) {
                    nodes.emplace(nodes.front()->left);
                }
                if(nodes.front()->right) {
                    nodes.emplace(nodes.front()->right);
                }
                nodes.pop();
            }
            if(level%2==1) {
                reverse(cur_level.begin(), cur_level.end());
            }
            level++;
            result.emplace_back(cur_level);
        }
        return result;
    }
};