Binary Tree Zigzag Level Order Traversal Problem
Description
LeetCode Problem 103.
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
1
2
Input: root = [1]
Output: [[1]]
Example 3:
1
2
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == NULL)
return ans;
queue<TreeNode*> bfsQ;
bfsQ.push(root);
int len = 1, cnt = 1;
vector<int> line;
TreeNode* curr;
while (!bfsQ.empty()) {
len = bfsQ.size();
line.clear();
for (int i = 0; i < len; i ++) {
curr = bfsQ.front();
bfsQ.pop();
if (curr != NULL) {
line.push_back(curr->val);
bfsQ.push(curr->left);
bfsQ.push(curr->right);
}
}
if (cnt % 2 == 0)
reverse(line.begin(), line.end());
cnt ++;
if (!line.empty())
ans.push_back(line);
}
return ans;
}
};