leetcode Question 15: Binary Tree Zigzag Level Order Traversal

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]
]

Analysis:

The idea is much similar to the previous question "Binary Tree Level Order Traversal", the only difference is the print order for each level. Note that we store the level order while traverse the tree, otherwise the print could be a mass. Just consider the order when pushing the values into the result vector. deque is a good STL container which can deal with double-end push and pop operation.


It is more easier to modify the "two queue" version of level-order travsersal. Details can be seen in the Python code. 

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res; //res vector
        if (root!=NULL){
            res.push_back(vector<int>(1,root->val)); // add root to the res
            deque<TreeNode*> q1,q2;
            vector<int> lev;
            q1.push_back(root);
            bool flag = false; //flag to decide the print order
            while (true){
                //level order traversal
                while (!q1.empty()){      
                    TreeNode* node = q1.front();
                    q1.pop_front();
                    if (node->left != NULL){q2.push_back(node->left);}
                    if (node->right != NULL){q2.push_back(node->right);}
                }
                if (q2.empty()){return res;}
                q1 = q2;
                //zigzag order print
                while (!q2.empty()){
                    if (flag){
                        lev.push_back(q2.front()->val);
                        q2.pop_front();
                    }else{
                        lev.push_back(q2.back()->val);
                        q2.pop_back();
                    }
                }
                res.push_back(lev);
                lev.clear();
                flag = !flag;
            }
        }
        
        return res;
        
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def zigzagLevelOrder(self, root):
        q1 = []
        q2 = []
        res = []
        if root == None:
            return res
        q1.append(root)
        l = []
        forward = True
        while True:
            while len(q1) !=0 :
                node = q1.pop(0)
                if node.left != None:
                    q2.append(node.left)
                if node.right != None:
                    q2.append(node.right)
                if forward == True:
                    l.append(node.val)    
                else:
                    l.insert(0, node.val)
            res.append(l)
            l = []
            q1 = q2
            q2 = []
            forward = not forward
            if len(q1) == 0:
                return res;