假设根节点处深度为 1.
①：层序遍历，存储。对所有深度为偶数的进行一次反转。
②：用两个双端队列 deq1，deq2. 当在奇数层进行 push 的时候，先 push_front 左儿子，再 push_front 右儿子；偶数层则与其相反 (push_front 进 deq2)。。当 deq1 为空时，deq1.swap(deq2)
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ret; queue<pair<TreeNode *, int>> que; if(root) que.push({root, 1}); while(!que.empty()) { auto top = que.front(); que.pop(); if(ret.size() == top.second) ret.back().emplace_back(top.first -> val); else { ret.push_back({top.first -> val}); } if(top.first -> left) que.push({top.first -> left, top.second + 1}); if(top.first -> right) que.push({top.first -> right, top.second + 1}); } for(int i = 1; i < ret.size(); i += 2) { reverse(ret[i].begin(), ret[i].end()); } return ret; } };
class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ret; deque<pair<TreeNode *, int>> que, que1; if(root) que.emplace_back(root, 1); while(!que.empty()) { auto top = que.front(); que.pop_front(); if(ret.size() == top.second) ret.back().emplace_back(top.first -> val); else { ret.push_back({top.first -> val}); } if(top.second % 2) { if (top.first->left) { que1.emplace_front(top.first->left, top.second + 1); } if (top.first->right) { que1.emplace_front(top.first->right, top.second + 1); } } else { if (top.first->right) { que1.emplace_front(top.first->right, top.second + 1); } if (top.first->left) { que1.emplace_front(top.first->left, top.second + 1); } } if(que.empty()) que.swap(que1); } return ret; } };