107. Binary Tree Level Order Traversal II

Description

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

Intuition

The problem requires a level order traversal, but instead of starting from the root, the final output should be from the bottom-most level to the top. This suggests that a regular level order traversal can be performed, but the result should be reversed before returning it.

Approach

1. Breadth-First Search (BFS): - Use a queue to perform BFS, which allows processing the tree level by level. - Start by adding the root node to the queue. - While the queue is not empty, process each level by iterating over the nodes currently in the queue. - For each node, record its value, and add its left and right children to the queue for processing in the next iteration. - Store the values of each level in a list.
2. Reverse the Result: - Once all levels have been processed and stored in a list of lists, reverse the list to get the bottom-up order. - Return the reversed list as the final result.

Complexity

Time Complexity:

(O(n)), where n is the number of nodes in the tree. Each node is visited once during the BFS.

Space Complexity:

(O(n)), where n is the number of nodes. This is due to the space required to store the output list and the queue used for BFS.

Code

C++

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        if (!root) return {};

        vector> levels;
        queue q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            vector level;

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* currentNode = q.front();
                q.pop();

                if (currentNode->left) q.push(currentNode->left);
                if (currentNode->right) q.push(currentNode->right);

                level.push_back(currentNode->val);
            }

            levels.push_back(level);
        }

        reverse(levels.begin(), levels.end());
        return levels;
    }
};

Python

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        levels = []
        queue = deque([root])

        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

                level.append(node.val)

            levels.append(level)

        return levels[::-1]

Java

class Solution {
    public List> levelOrderBottom(TreeNode root) {
        List> levels = new ArrayList<>();
        if (root == null) return levels;

        Queue queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List level = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();

                if (currentNode.left != null) queue.add(currentNode.left);
                if (currentNode.right != null) queue.add(currentNode.right);

                level.add(currentNode.val);
            }

            levels.add(level);
        }

        Collections.reverse(levels);
        return levels;
    }
}

JavaScript

const levelOrderBottom = (root) => {

    if (!root) return [];
    const levels = [];
    const queue = [root];

    while (queue.length) {
        const level = [];
        const queueLength = queue.length;
        
        for (let i = 0; i < queueLength; i++) {
            const currentNode = queue.shift();
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
            level.push(currentNode.val)
        }
        levels.push(level);
    }
    return levels.reverse();
};