Binary Tree Level Order Traversal II

Problem Statement

In this task, we are dealing with a binary tree. The goal is to perform a traversal that records the values of nodes level by level, starting from the leaf nodes and moving up to the root. This order of traversal is known as a bottom-up level order traversal. Each level's node values should be listed from left to right, and the levels themselves should be listed from bottom (leaf) to top (root). The challenge involves both understanding the structure of the given binary tree and implementing an algorithm to traverse and record values in the required order.

Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

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

Example 2

Input:

root = [1]

Output:

[[1]]

Example 3

Input:

root = []

Output:

[]

Constraints

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

Approach and Intuition

To tackle this problem, the ideal way is to use Breadth-First Search (BFS) due to its nature of exploring nodes level by level. However, since we need a bottom-up level order, we will modify our approach to reverse the typical top-down level order result.

1. First, check if the root is null. If so, return an empty list as there are no nodes to traverse.
2. Initialize a queue to help with BFS traversal. This queue will store nodes along with their corresponding tree level.
3. Use a list (or deque for efficiency) to hold the final results and a temporary list for nodes at the current level.
4. As you dequeue nodes, enqueue their child nodes (left first, then right).
5. Once an entire level is processed, append the list of node values for that level to the beginning of your result list. This will ensure that the bottom-most level ends up at the end of the result list, effectively reversing the order without additional operations.
6. Continue the BFS until you've processed all levels of the tree.
7. Return the list containing the reversed levels.

Some key points to note:

• The input tree may have 0 nodes, in which case we immediately return an empty list.
• Node values can range from -1000 to 1000, which doesn't affect the traversal or recording mechanism but is essential to ensure the traversal algorithm handles the range correctly.
• The tree can have a maximum of 2000 nodes, meaning the BFS will perform efficiently within this limit.

Solutions

class Solution {
public:
    vector<vector<int>> bottomUpLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        deque<TreeNode*> queue_next;
        queue_next.push_back(root);
        while (!queue_next.empty()) {
            deque<TreeNode*> queue_current = queue_next;
            queue_next.clear();
            result.push_back(vector<int>());
            for (TreeNode* node : queue_current) {
                result.back().push_back(node->val);
                if (node->left) queue_next.push_back(node->left);
                if (node->right) queue_next.push_back(node->right);
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};