103. Binary Tree Zipzag Level Order Traversal

Given a binary tree, return thezigzag level ordertraversal 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]
]

Thoughts:

1. order to expanding which node's child in the current level -> using stack<TreeNode*> to reverse the order.

2. for each Node in the current level, decide weather to first push left or right into the queue:

   1. curDepth is odd -> next level even -> Normal Order

   2. curDepth is even -> next level odd -> reverse Order

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> answer;
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue <TreeNode *> q;
        stack<TreeNode *> levelNode;
        if(!root) return answer;

        q.push(root);
        int curDepth = 0;
        while(!q.empty()){
            int len = q.size();
            vector<int> level;
            for(int i = 0 ; i < len; i ++){
                TreeNode * cur = q.front();
                // visit
                level.push_back(cur->val);
                levelNode.push(cur);
                q.pop();
            }
            answer.push_back(level);
            // add child
            for(int i = 0; i < len; i++){
                TreeNode * cur = levelNode.top();levelNode.pop();
                if(curDepth %2 ==0){
                    if(cur->right) q.push(cur->right);
                    if(cur->left) q.push(cur->left);
                }
                else{

                    if(cur->left) q.push(cur->left);
                    if(cur->right) q.push(cur->right);
                }
            }

            curDepth++;
        }

        return answer;
    }
};

Code (Python)

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        res, temp, q, flag=[], [], [root], 1
        while q:
            for i in xrange(len(q)):
                node=q.pop(0)
                temp+=[node.val]
                if node.left: q+=[node.left]
                if node.right: q+=[node.right]
            res+=[temp[::flag]] // flag decides what is the final order being added!
            temp=[]
            flag*=-1
        return res

Special Thanks fangkunjnsy for the reference