LeetCode 107: Binary Tree Level Order Traversal II Solution

Master LeetCode problem 107 (Binary Tree Level Order Traversal II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

107. Binary Tree Level Order Traversal II

Medium

Tree Breadth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a level order traversal of the binary tree and then reverse the result to obtain the bottom-up level order traversal. We can use a queue data structure to perform the level order traversal.

Initialize a queue to store nodes at each level.
Start with the root node and add it to the queue.
While the queue is not empty, iterate over the nodes at the current level, add their values to the current level list, and add their children to the queue for the next level.
After processing all nodes at the current level, add the current level list to the result list.
Finally, reverse the result list to get the bottom-up level order traversal.

Time Complexity: O(n) where n is the number of nodes in the binary tree. We visit each node exactly once.

Space Complexity: O(n) where n is the number of nodes in the binary tree. In the worst case, the queue can contain all nodes at the last level.

Solution Code

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelValues = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelValues.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            result.add(0, levelValues); // Add the level values at the beginning to reverse the order
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 107 (Binary Tree Level Order Traversal II)?

This page provides optimized solutions for LeetCode problem 107 (Binary Tree Level Order Traversal II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 107 (Binary Tree Level Order Traversal II)?

The time complexity for LeetCode 107 (Binary Tree Level Order Traversal II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 107 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 107 in Java, C++, or Python.

Back to LeetCode Solutions