**Difficulty: Medium**

**Frequency: N/A**

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,#,#,15,7}`

,

3 / \ 9 20 / \ 15 7

return its zigzag level order traversal as:

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

**My solution:**

**Data structure:**

**Steps:**

**Complexity:**

Runtime:

Space:

**Test cases:**

**Corner cases:**

**Code:**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> results; if (!root) return results; deque<TreeNode*> deq; deq.push_front(root); bool front = true; while (!deq.empty()) { int s_size = deq.size(); vector<int> result; while (s_size) { if (front) { TreeNode *cur = deq.front(); deq.pop_front(); result.push_back(cur->val); if (cur->left) deq.push_back(cur->left); if (cur->right) deq.push_back(cur->right); } else { TreeNode *cur = deq.back(); deq.pop_back(); result.push_back(cur->val); if (cur->right) deq.push_front(cur->right); if (cur->left) deq.push_front(cur->left); } s_size--; } front = !front; results.push_back(result); } return results; } };

**Another solution:**

**Data structure:**

**steps:**

**Complexity**:

Runtime:

Space:

**Code**:

**Things to learn:**

[…] Binary Tree Zigzag Level Order Traversal […]

LikeLike