给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） 例如： 给定的二叉树是{3,9,20,#,#,15,7},
该二叉树之字形层序遍历的结果是
[
[3],
[20,9],
[15,7]
]
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int> > zigzagLevelOrder(TreeNode* root) { // write code here vector<vector<int>> res; if(root == NULL) return res; deque<TreeNode*> dq; //int level = 0; bool flag=true; TreeNode* head = root; dq.push_back(head); while(!dq.empty()){ vector<int> tmp; int size = dq.size(); while(size--){ if(flag){ TreeNode* cur = dq.front(); tmp.push_back(cur->val); dq.pop_front(); if(cur->left) dq.push_back(cur->left); if(cur->right) dq.push_back(cur->right); }else{ TreeNode* curnode = dq.back(); tmp.push_back(curnode->val); dq.pop_back(); if(curnode->right) dq.push_front(curnode->right); if(curnode->left) dq.push_front(curnode->left); } } flag = !flag; res.push_back(tmp); } return res; } };
class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int> > zigzagLevelOrder(TreeNode* root) { // write code here vector<vector<int>> res; if(root == NULL) return res; queue<TreeNode*> dq; int level =1; bool lr = true; TreeNode* last = root; TreeNode* nLast = NULL; dq.push(root); while(!dq.empty()){ int size = dq.size(); vector<int> tmp; while(size--){ TreeNode *node = dq.front(); dq.pop(); tmp.push_back(node->val); if(node->left) dq.push(node->left); if(node->right) dq.push(node->right); } if(!lr){ reverse(tmp.begin(), tmp.end()); } res.push_back(tmp); lr = !lr; } return res; } };
