103. Binary Tree Zigzag Level Order Traversal

Typical level order traversal problem. We only need to keep a variable to know if we need to print from left to right or vice versa.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (root == NULL) return res;  
15:      queue<TreeNode*> que;  
16:      bool ltor = true;  
17:      que.push(root);  
18:      while (!que.empty()) {  
19:        int n = que.size();  
20:        vector<int> row(n, 0);  
21:        for (int i = 0; i < n; i++) {  
22:          TreeNode *node = que.front();  
23:          que.pop();  
24:          int pos = ltor ? i : n-i-1;  
25:          row[pos] = node->val;  
26:          if (node->left) que.push(node->left);  
27:          if (node->right) que.push(node->right);  
28:        }  
29:        ltor = !ltor;  
30:        res.push_back(row);  
31:      }  
32:      return res;  
33:    }  
34:  };