Leetcode: Binary Tree Level Order Traversal II

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the problem:

The problem asks for traverse the binary tree in order. The mainly difference between the BFS is it asks for returning the result bottom-up.

Naive Solution:

One native solution is to still use the pre-order traversal of the tree, and save the level, like how we solved the BFS problem recursively. The major difference is instead of appending the list of each level, we add them at front of the result list, and move others forward. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        levelOrderBottom(root, result, 1);
        
        return result;
    }
    
    private void levelOrderBottom(TreeNode root, ArrayList<ArrayList>Integer>> result, int level) {
        if (root == null) return;
        
        if (result.size() < level) {
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            levelList.add(root.val);
            result.add(0, levelList);
        } else {
            result.get(result.size() - level).add(root.val);
        }
        
        levelOrderBottom(root.left, result, level + 1);
        levelOrderBottom(root.right, result, level + 1);
    }
}

Discussion:
Now let's analyze the complexity. Traversing all nodes of the tree takes O(n) time. However, adding the level list at the beginning of the result list and moving the rest behind takes O(n) time as well. So the overall time complexity is O(n^2).

A Better Solution:
Now that we know the time complexity is O(n^2), can we traverse the tree bottom-up, then append it to the array will takes only O(1) time thus the overall time complexity would be O(n). So far I was unabA Better Solution:
Now that we know the time complexity is O(n^2), can we traverse the tree bottom-up, then append it to the array will takes only O(1) time thus the overall time complexity would be O(n). 

So far I was unable to find a method to traverse the tree in level order bottom-up. It is hard to address the following tree
      1
     /  \
   2   3
        /  \
      15  7
If do the post-order traverse, it will start from 2 instead of 15. 

Iterative Solution:
The iterative solution for BFS is to use a queue. The idea is for each node, we enqueue all its left and right children into the queue, and dequeue all of them in next level. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelList.add(curr.val);
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            result.add(0, levelList);
        }                      
        return result;
    }
} 

Summary:
Note the iterative solution of the BFS, be very familiar with the details. In addition, one possible O(n) solution for the bottom-up traversal is to do the top-down traversal first and get the final result list. Then reverse the list in-place. Since reversing the list takes O(n) time as well, the overall time complexity is still O(n).