就是二叉树的层序遍历,我记得这题,用栈用队列,然后有个关键的size()
Ⅰ
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> temp;
temp.push(root);
while (!temp.empty()) {
int level = temp.size();
for (int i = 0; i < level; i++) {
TreeNode* node = temp.front();
temp.pop();
if (node->left) temp.push(node->left);
if (node->right) temp.push(node->right);
res.push_back(node->val);
}
}
return res;
}
Ⅱ
Ⅱ要求一行一行打印,那不就是我第一题的做法,那么…也就是说第一题还有更简单的做法?
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> temp;
temp.push(root);
while (!temp.empty()) {
int level = temp.size();
res.push_back(vector<int>());
for (int i = 0; i < level; i++) {
TreeNode* node = temp.front();
temp.pop();
if (node->left) temp.push(node->left);
if (node->right) temp.push(node->right);
res.back().push_back(node->val);
}
}
return res;
}
Ⅲ
之字形打印,这题和力扣103是一样的
翻书提示:用两个栈
之前就有用两个栈模拟队列的题目,但是如果按照原来的思路,那这和直接用队列有什么区别?
这里还是根据奇偶分了情况的,只是…这样的话为什么我不直接reverse()
…
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> temp;
temp.push(root);
bool reverseFlag = false;// 奇数偶数切换标志
while (!temp.empty()) {
int level = temp.size();
res.push_back(vector<int>());
for (int i = 0; i < level; i++) {
TreeNode* node = temp.front();
temp.pop();
if (node->left) temp.push(node->left);
if (node->right) temp.push(node->right);
res.back().push_back(node->val);
}
if (reverseFlag) reverse(res.back().begin(), res.back().end());
reverseFlag = !reverseFlag;
}
return res;
}
直接reverse()
效率还挺高
再来看看书上的做法
它这里不是在两个栈之间倒腾——就是不存在从栈1拿出来又压到栈2(用两个栈模拟队列的做法)
而是分奇偶两种压法:先左后右/先右后左
至于为什么要两个栈,是因为在操作一个栈弹栈的过程总不能在往这个栈压,不然会破坏顺序,所以需要另外一个栈
…看起来好像也没有那么高明…但是没想到?
class Solution {
private:
stack<TreeNode*> stk1, stk2;
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
stk1.push(root);
bool level = false;
while (!stk1.empty() || !stk2.empty()) {
res.push_back(vector<int>());
if (level) {
// 偶数层
while (!stk2.empty()) {
TreeNode* node = stk2.top();
stk2.pop();
if (node->right) stk1.push(node->right);
if (node->left) stk1.push(node->left);
res.back().push_back(node->val);
}
}
else {
// 奇数层
while (!stk1.empty()) {
TreeNode* node = stk1.top();
stk1.pop();
if (node->left) stk2.push(node->left);
if (node->right) stk2.push(node->right);
res.back().push_back(node->val);
}
}
level = !level;
}
return res;
}
};
感觉代码重复度有点高,洁癖犯了
标签:node,temp,Offer,res,back,力扣,二叉树,push,root From: https://www.cnblogs.com/yaocy/p/17102806.html