二叉树的之字形层序遍历
二叉树的之字形层序遍历
http://www.nowcoder.com/questionTerminal/47e1687126fa461e8a3aff8632aa5559
/** * 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) { // 和按层次遍历一样,只是这道题遇到偶数行需要翻转,使用一个标记位标记一下就可以了 vector<vector<int> > ans; if (root == nullptr) return ans; queue<TreeNode*> q; q.emplace(root); bool flag = true; while(!q.empty()) { int sz = q.size(); vector<int> level; for (int i = 0; i < sz; i++) { TreeNode* node = q.front(); q.pop(); level.emplace_back(node->val); if (node->left) q.emplace(node->left); if (node->right) q.emplace(node->right); } if (!flag) { reverse(level.begin(), level.end()); } ans.emplace_back(level); flag = !flag; } return ans; } };