🎨 Try our Free AI Image Generation Feature

107. Binary Tree Level Order Traversal II

avatar
Dare2Solve

10 months ago

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();
};