/** * 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) {        vector<vector<int> > res;        if (root == NULL) return res;        res.push_back(vector<int>(1, root->val));                vector<TreeNode*> pre_level(1, root);        vector<TreeNode*> cur_level;        bool l2r = true;                while (!pre_level.empty()) {            res.push_back(vector<int>());            int plen = pre_level.size();                        TreeNode* node = NULL;                        for (int i=0; i<plen; i++) {                node = pre_level[i];                if (node->left != NULL) {                    res.back().push_back(node->left->val);                    cur_level.push_back(node->left);                }                if (node->right != NULL) {                    res.back().push_back(node->right->val);                    cur_level.push_back(node->right);                }            }            if (l2r) {                reverse(res.back().begin(), res.back().end());                //reverse(cur_level.begin(), cur_level.end());            }                        pre_level.clear();            swap(pre_level, cur_level);                        if (pre_level.empty()) res.pop_back();            l2r = !l2r;        }                return res;    }};