# Binary-Tree-Zigzag-Level-Order-Traversal

Feb 11, 2018

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

    3
/ \
9  20
/  \
15   7


return its zigzag level order traversal as:

[
[3],
[20,9],
[15,7]
]


void levelTra(TreeNode *root) {
if (root == nullptr) return ;
queue<TreeNode *> q;
q.push(root);
while(!q.empty()) {
root = q.front(); q.pop();
cout << root->val;
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}


void levelTra(TreeNode *root) {
if (root == nullptr) return ;
queue<TreeNode *> q;
q.push(root);
q.push(nullptr);
while(true) {
root = q.top(); q.pop();

if (root == nullptr) {
cout << "new level" << endl;
if (q.empty()) break;
q.push(nullptr);
}

cout << root->val << endl;
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}
}

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > ret;
vector<int> tmp;
if (root == nullptr) return ret;
//level tra

bool flag = true; //判断遍历方向

queue<TreeNode *> q;
q.push(root);
q.push(nullptr);

while(true) {
root = q.front(); q.pop();
if (root == nullptr)  {

if (flag) ret.push_back(tmp);
else ret.push_back(vector<int>(tmp.rbegin(), tmp.rend()));

tmp.clear();
flag = !flag;

if (q.empty()) break;
q.push(nullptr);
continue;
}

tmp.push_back(root->val);
if (root->left) q.push(root->left);
if (root->right) q.push(root->right);
}

return ret;
}


void travel(TreeNode *root, vector<vector<int> > &ret, int level) {
if (root == nullptr) return ;
if (level >= ret.size()) ret.push_back(vector<int>());

ret[level].push_back(root->val);

travel(root->left, ret, level + 1);
travel(root->right, ret, level + 1);
}

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int>> ret;
travel(root, ret, 0);

for(int i = 0;i < ret.size();i++) {
if (i % 2) reverse(ret[i].begin(), ret[i].end());
}

return ret;
}



Update as 2020-03-28

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > res;
int level = 0;
stack<TreeNode*> st_even, st_odd;
if (root) st_even.push(root);
while(!st_even.empty() || !st_odd.empty()) {
stack<TreeNode*> &st1 = level % 2 == 0 ? st_even : st_odd;
stack<TreeNode*> &st2 = level % 2 == 0 ? st_odd : st_even;
vector<int> temp;
for(int i = 0, size = st1.size(); i < size; i++) {
root = st1.top(); st1.pop();
temp.push_back(root->val);

TreeNode *left = root->left, *right = root->right;
if (level % 2) swap(left, right);

if (left) st2.push(left);
if (right) st2.push(right);
}
//cout << st1.size() << " " << st2.size() << endl;
res.push_back(temp);
level++;
}
return res;
}

LeetCodeLeetCodeTreeQueuesStackBFS

Flatten-Nested-List-Iterator

Search-a-2D-Matrix-II