103. Binary Tree Zigzag Level Order Traversal

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:

One thought on “103. Binary Tree Zigzag Level Order Traversal

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s