LeetCode: 107. Binary Tree Level Order Traversal II

The Problem

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

Example

Input:  [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> ans;
    levelOrderBottomHelper(root, ans, 0);

    reverse(ans.begin(), ans.end());

    return ans;
}

void levelOrderBottomHelper(
TreeNode* root, vector<vector<int>> &levels, int level
) {
    if ( root == nullptr) return;

    int nextLevel = level + 1;

    if(levels.size() < nextLevel) 
    levels.resize(nextLevel);

    levelOrderBottomHelper(root->left, levels, nextLevel);
    levelOrderBottomHelper(root->right, levels, nextLevel);

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

Let's break down the code step by step:

1. vector<vector<int>> levelOrderBottom(TreeNode* root): This is the main function that initiates the process. It takes the root of the binary tree as an argument.
2. vector<vector<int>> ans;: ans is a 2D vector that will store the result of the bottom-up level order traversal.
3. levelOrderBottomHelper(root, ans, 0);: This line calls the helper function levelOrderBottomHelper to perform the traversal. It starts at the root of the tree with level 0.
4. reverse(ans.begin(), ans.end());: After the traversal is complete, this line reverses the ans vector. This reversal is necessary because the traversal builds the result from top to bottom, so reversing it at the end gives the desired bottom-up order.
5. return ans;: The reversed ans vector is returned as the final result.

Now, let's look at the levelOrderBottomHelper function:

1. void levelOrderBottomHelper(TreeNode* root, vector<vector<int>> &levels, int level): This is the recursive helper function that performs the traversal.
2. if (root == nullptr) return;: If the root node is null (indicating an empty subtree), the function returns immediately.
3. int nextLevel = level + 1;: nextLevel is incremented to keep track of the next level in the traversal.
4. if (levels.size() < nextLevel) levels.resize(nextLevel);: This code ensures that there is enough space in the levels vector to store values for the current level. If not, it resizes the levels vector to accommodate the new level.
5. levelOrderBottomHelper(root->left, levels, nextLevel);: Recursive call to traverse the left subtree, passing the updated level.
6. levelOrderBottomHelper(root->right, levels, nextLevel);: Recursive call to traverse the right subtree, passing the updated level.
7. levels[level].push_back(root->val);: This line adds the value of the current node (root->val) to the appropriate level in the levels vector. The level variable determines which level to add the value to.