107. Binary Tree Level Order Traversal II

Description

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [3, 9, 20, null, null, 15, 7]

Output:

[

[15, 7],

[9, 20],

[3]

]

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Solution 1

/**
 * Time complexity : O(N) since each node is processed exactly once.
 * Space complexity : O(N) to keep the output structure which contains N 
 *    node values.
 */

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList();
        if(root != null) {
            levelOrderBottom(resultList, root, 0);
            Collections.reverse(resultList);
        }
        return resultList;
    }
    
    private void levelOrderBottom(List<List<Integer>> resultList,
                                  TreeNode node,
                                  int level) {
        if(resultList.size() == level) {
            resultList.add(new ArrayList<Integer>());
        }
        
        resultList.get(level).add(node.val);
        
        if(node.left != null) {
            levelOrderBottom(resultList, node.left, level+1);
        }
        
        if(node.right != null) {
            levelOrderBottom(resultList, node.right, level+1);
        }
    }
}

Follow up

• Level order traversal in spiral form - GFG
• Reverse Level Order traversal in spiral form - GFG