Day 5 : 107. Binary Tree Level Order Traversal II

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

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 iterate through the map IN REVERSE!!!!

Step by Step solution!

Complete Solution :

class Solution {
public:
     map<int, vector<int>> LeveNodes; // key: level, value: nodes of level
    
    void InOrder(TreeNode* root, int level) {
        if (root != nullptr) {
            InOrder(root->left, level + 1);
            LeveNodes[level].push_back(root->val);
            InOrder(root->right, level + 1);
        }
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        InOrder(root, 0);
        vector<vector<int>> result;

        // loop through the reverse map and push_back
        for (auto it = LeveNodes.rbegin(); it != LeveNodes.rend(); ++it) {
            result.push_back(it->second);
        }
        return result;
    }
};

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. Write a letter to your future self, remembering all the fights you had to get where you are

2. Create something to look forward to tomorrow, for me its coffee!!!

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!