Day 4 : 103. Binary Tree Zigzag Level Order Traversal

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).

Before we dive in,

Breathe

Nothing is ever that deep.

Now, let’s

But there is a little trick that I am about to teach you….

We’re going to leverage recursion to navigate through the tree and a map to store the nodes level by level, where the key is the level and the value is an array with the nodes in that level.

We are simply going to iterate through the tree INORDER, and store in our map the current node we are processing and their level:

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

And every time we call our recursive function, we’re simply going to add 1 to our level so that when we traverse deeper into the tree, we know exactly where we are:

auxLevelOrder(root->left, level + 1); 
auxLevelOrder(root->right, level + 1);

This approach allows us to group nodes together INORDER by their levels as we go down the tree.

Once we build our map of levels and their respective nodes, we loop through each level, reversing the nodes on odd levels to achieve the zigzag pattern.

Step by Step solution!

Complete Solution :

class Solution {
public:
    map<int, vector<int>>nodes_by_level;

    void auxZigzagLevelOrder(TreeNode* root, int level){
        if (root==NULL){
            return;
        }
        auxZigzagLevelOrder(root->left, level+1); 
        nodes_by_level[level].push_back(root->val); 
        auxZigzagLevelOrder(root->right, level+1); 
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>nodes_by_zigzag;
        auxZigzagLevelOrder(root, 0); 
        for(const auto&[key,val]: nodes_by_level){
            if(key%2==0){
                nodes_by_zigzag.push_back(val);
            }
            else{
                vector<int> temp = val;
                reverse(temp.begin(), temp.end());
                nodes_by_zigzag.push_back(temp);
            }
        }
        return nodes_by_zigzag;
    }

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. How to master an interview

2. Steal Taylor Swift’s habit that made her a music powerhouse

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!