题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
-
树中节点数目在范围
[0, 2000]内 -
-100 <= Node.val <= 100
思路
参考层次遍历，现在多了一条奇数行要反着来。同样可以使用队列和递归两种方式。
// 递归：先层次遍历，再翻转奇数行
vector<vector<int>> zigzagLevelOrder1(TreeNode* root) {
vector<vector<int>> ans;
auto travel = [&](this auto&& travel, TreeNode* node, int depth) {
if (!node) return;
if (ans.size() <= depth) {
ans.resize(depth + 1);
}
ans[depth].push_back(node->val);
travel(node->left, depth + 1);
travel(node->right, depth + 1);
};
travel(root, 0);
// 反转奇数行
for (int i = 0; i < ans.size(); ++i) {
if (i & 1) {
std::reverse(ans[i].begin(), ans[i].end());
}
}
return ans;
}
// 循环：用队列辅助，bfs
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int depth = ans.size();
int n = q.size(); // 这一层有n个元素
vector<int> vals(n);
for (int i = 0; i < n; ++i) {
auto p = q.front();
q.pop();
// 奇数层反着来
vals[depth & 1 ? n - 1 - i : i] = p->val;
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
ans.push_back(std::move(vals));
}
return ans;
}