103. Binary Tree Zigzag Level Order Traversal
上一题递归做的，这题也可以递归做，同样也是线性复杂度，但是递归的效率肯定比较低，所以这次也提供用队列和栈的解法。
递归版本，就是在102解法的基础上，将ans的行按照奇数反向reverse：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
pre(root, 0, ans);
for (int i = 0; i < ans.size(); i++) {
if (i % 2 == 1) reverse(ans[i].begin(), ans[i].end());
}
return ans;
}
void pre(TreeNode *root, int depth, vector<vector<int>> &ans) {
if (!root) return ;
if (depth >= ans.size()) ans.push_back(vector<int> {});
ans[depth].push_back(root->val);
pre(root->left, depth + 1, ans);
pre(root->right, depth + 1, ans);
}
};
非递归版本，双栈。。。讲下思路：
- 利用栈1
s1储存奇数层的点，s2储存偶数层的点，所以根结点就储存在s2里； - 当前层为偶数层时，说明此时
s1是空的，为了让下一层结点从s1出来的时候从右到左，所以让左结点先进栈，毕竟先进后出嘛； - 当前层为奇数层时，说明此时
s2是空的，且s1结点出来时从右到左，为了让下一层结点从s2出来的时候从左到右，所以让右结点先进栈，先进后出； - 其他的没什么好说的了，记得每次层数+1，将本层结点用一个vector储存。。。
代码：
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
stack<TreeNode *> s1, s2;
s2.push(root);
int depth = 0;
while (!s1.empty() || !s2.empty()) {
vector<int> v;
TreeNode *it = NULL;
if (depth % 2 == 0) {
while (!s2.empty()) {
it = s2.top();
v.push_back(it->val);
if (it->left) s1.push(it->left);
if (it->right) s1.push(it->right);
s2.pop();
}
} else {
while (!s1.empty()) {
it = s1.top();
v.push_back(it->val);
if (it->right) s2.push(it->right);
if (it->left) s2.push(it->left);
s1.pop();
}
}
depth++;
ans.push_back(v);
}
return ans;
}
};
