题目描述
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
题目描述
层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
bool isOrder = true;
while (!q.empty()) {
int curLevelSize = q.size();
res.push_back(vector<int>(curLevelSize));
for (int i = 0; i < curLevelSize; ++i) {
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
if (isOrder) res.back()[i] = node->val;
else res.back()[curLevelSize - 1 - i] = node->val;
}
isOrder = !isOrder;
}
return res;
}
};
|
时间复杂度 O(n)，空间复杂度 O(n)
