Binary Tree Level Order Traversal II

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

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 \leq \text{Node.val} \leq 1000$

Solution Code

Python

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
    
        if not root:
            return result
    
        queue = [root]
    
        while queue:
            level_size = len(queue)
            current_level = []
        
            for _ in range(level_size):
                node = queue.pop(0)
                current_level.append(node.val)
            
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
            result.insert(0, current_level)
    
        return result

Java

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        levelOrderTraversal(root, lists);
        Collections.reverse(lists);
        return lists;
    }
    
    void levelOrderTraversal(TreeNode root, List<List<Integer>> lists) {
        if (root == null) {
            return;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
            lists.add(level);
        }
    }
}

C++

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if (!root)  return {};
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL);
        vector<int> temp;

        while(!q.empty()){
            auto it=q.front();
            q.pop();
            if (it)
                temp.push_back(it->val);
            if (!it){
                ans.push_back(temp);
                temp.clear();
                if (!q.empty())
                    q.push(NULL);
            }
            else{
                if (it->left)
                    q.push(it->left);
                if (it->right)
                    q.push(it->right);
            }

        }
        reverse(ans.begin(),ans.end());
        return ans;
    }//Hope you would have got it!
};

Javascript

var levelOrderBottom = function (root) {
    if(!root) return [];
    
    const results = [];
    const queue = [root];
    
    while(queue.length){
        const current_level_length = queue.length;
        const current_level_values = [];
        
        for(let i=0; i < current_level_length; i++){
            const node = queue.shift();
            current_level_values.push(node.val)    
            if(node.left)  queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
        results.unshift(current_level_values)
    }

    return results; // we could have use .reverse() here, but using shift is o(n) & faster, whereas sort is n logn
}