32-III. 从上到下打印二叉树 III
1. 描述
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
2. 例子
示例 1:
给定二叉树: [3,9,20,null,null,15,7],
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
3. 提示
- 节点总数 <= 1000
4. 题解
n 是 i_root 中的节点数目
时间复杂度: O(n)
空间复杂度: O(n)
class Solution {
public:
// vector<vector<int>> levelOrder(TreeNode* root)
vector<vector<int>> levelOrder(TreeNode *i_root)
{
if(!i_root) return vector<vector<int>>{};
queue<TreeNode *> currentLayer{{i_root}};
queue<TreeNode *> nextLayer;
vector<vector<int>> prints;
vector<int> levelPrints;
while(!currentLayer.empty() || !nextLayer.empty())
{
if(currentLayer.empty())
{
prints.push_back(move(levelPrints));
swap(currentLayer, nextLayer);
}
else
{
auto node = currentLayer.front();
currentLayer.pop();
levelPrints.push_back(node->val);
if(node->left) nextLayer.push(node->left);
if(node->right) nextLayer.push(node->right);
}
}
prints.push_back(move(levelPrints));
for(int i = 1; i < prints.size(); i += 2)
reverse(prints[i].begin(), prints[i].end());
return prints;
}
};