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,#,#,15,7},
3 / \ 9 20/ \ 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7]]
题目还是比较简单，主要就是一个层次扫描然后进行翻转的过程
这里有点类似层序扫描，在层序扫描中主要是利用了一个queue进行存储节点，，然后读出对应的val，这里需要返回的类型需要具体按层给出，所以就需要用到一个vector将每一层的节点进行记录
/** * 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>> res;int flag= 0;vector<vector<int> > zigzagLevelOrder(TreeNode *root) {res.clear();if(root == NULL){return res;}vector<TreeNode*>pNode;pNode.push_back(root);vector<int> tmp;tmp.push_back(root->val);res.push_back(tmp);flag++;getNode(pNode);return res;}void getNode(vector<TreeNode*> &pNode){if(pNode.empty()){return;}vector<TreeNode*> Node;vector<TreeNode*>::iterator it = pNode.begin();vector<int> tmp;for(;it != pNode.end();it++){TreeNode * root = *it;if(root->left){tmp.push_back(root->left->val);Node.push_back(root->left);}if(root->right){tmp.push_back(root->right->val);Node.push_back(root->right);}}if(tmp.empty()){return; //<没有孩子节点，可以返回}if(flag&1){reverse(tmp.begin(),tmp.end());}flag++;res.push_back(tmp);getNode(Node);}};主要是利用了一个vector的翻转操作
还看到一个用queue进行操作的方法，这里是在每一层操作的最后面放上一个NULL节点，用于判断这一层的数据解完了
/** * 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> > result;vector<int> temp;result.clear();if(root==NULL)return result;queue<TreeNode *> pTemp;int flag=0;pTemp.push(root);pTemp.push(NULL);while(!pTemp.empty()){TreeNode *curNode=pTemp.front();pTemp.pop();if(curNode!=NULL){temp.push_back(curNode->val);if(curNode->left)pTemp.push(curNode->left);if(curNode->right)pTemp.push(curNode->right);}else{if(!temp.empty()){pTemp.push(NULL);if(flag==1){reverse(temp.begin(),temp.end());}result.push_back(temp);flag=1-flag;temp.clear();}}}return result;}};
往往教导我们大家要好好学习天天向上，要永不言弃坚持到底百折不挠宁死不屈，
