BinaryTreeLevelOrderTraversalII.java

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

// For example:
// Given binary tree [3,9,20,null,null,15,7],
//     3
//    / \
//   9  20
//     /  \
//    15   7
// return its bottom-up level order traversal as:
// [
//   [15,7],
//   [9,20],
//   [3]
// ] 

/* 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;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> level = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList(); 
        if(root == null)
            return result;
        
        queue.add(root);
        
        int numNodeCurrentLevel = 1; //used to record number of nodes in current level
        int numNodeNextLevel = 0; //used to record number of nodes in next level
        
        while(!queue.isEmpty()){
            TreeNode temp = queue.peek(); // will take out the elment which was added first in the queue and store it in temp
            queue.remove(); // remove the element from the queue
            level.add(temp.val); // add the value of temp in the level
            numNodeCurrentLevel--; 
          // Checkout values in temp.left and temp.right and store it in queue, also increase the counter for next level
            if(temp.left != null){
                queue.add(temp.left);
                numNodeNextLevel++;
            }
            if(temp.right != null){
                queue.add(temp.right);
                numNodeNextLevel++;
            }
          //if we have traversed the current level, go to next level
            if(numNodeCurrentLevel == 0){
                result.add(level); // add current list of levels in result
                level = new ArrayList<Integer>(); // initialize level again, so it can store list of only current level
                numNodeCurrentLevel = numNodeNextLevel; //assign the number of nodes in next level to current level
                numNodeNextLevel = 0; // set next level to zero
            }

        }
      //Now we are done with the level order traversal,
      //but for the final result we need to reverse it,
      //as we have to show levels from leaf to root
        List<List<Integer>> finalResult = new ArrayList<List<Integer>>();
         for(int i = result.size()-1; i>=0; i--){
        	finalResult.add(result.get(i));
        }

        return finalResult;
       
    }
}