中等难度题，如果使用最简单的层序遍历思想开数组层序遍历返回，空间复杂度会高一点；
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>>rvec;
queue<TreeNode*>que;
bool flag = true;
que.push(root);
while (!que.empty()) {
vector<int>mem_int;
size_t len = que.size();
for (size_t i = 0; i < len; i++) {
TreeNode* p = que.front();
que.pop();
if (p->left != NULL) {
que.push(p->left);
}
if (p->right != NULL) {
que.push(p->right);
}
mem_int.push_back(p->val);
}
if (!flag) {
reverse(mem_int.begin(), mem_int.end());
}
flag=!flag;
rvec.push_back(mem_int);
}
return rvec;
}
其实可以使用DFS，直接对res二维数组判断插在数组头部还是尾部；
本质原因是因为，先序DFS遍历可以保证同一层的元素必定先被访问；
所以只需要DFS+递归判断即可，决定该元素插入尾部还是首部；
vector<vector<int>>rvec;
void dfs(TreeNode* root, int level) {
if (root == NULL)
return;
if (level == rvec.size())
rvec.resize(level + 1);
if (level % 2 == 0) {
//正序输出；
rvec[level].push_back(root->val);
}
else {
//逆序输出；
rvec[level].insert(rvec[level].begin(),root->val);
}
dfs(root->left, level + 1);
dfs(root->right, level + 1);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
dfs(root, 0);
return rvec;
}
但是这种递归容易爆内存，这题没爆，不知道后续会不会有什么问题；
原文：https://www.cnblogs.com/songlinxuan/p/14171206.html