LeetCode 107 - Binary Tree Level Order Traversal II

https://leetcode.com/problems/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,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

In Java, one easy way is to insert the list into the head of the linkedlist. So at least it is not needed to reverse the list.

https://discuss.leetcode.com/topic/7489/simple-java-solution-with-linkedlist/6

It's trade off between ArrayList.add(0, List) and LinkedList.get(list.size()-1-level).

X. BFS
https://discuss.leetcode.com/topic/23994/java-solution-with-linkedlist

This solution is nearly identical to the traditional 'Level Order traversal' only difference is the DataStructure used to hold the data. Instead of Using an ArrayList and appending each level after the other I used a LinkedList and added each new level to the headof the LinkedList.

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) return new LinkedList<List<Integer>>();
        List<List<Integer>> levels = new LinkedList<List<Integer>>();
        Queue<TreeNode> q = new LinkedList<TreeNode>(); 
        q.add(root);
        
        while(!q.isEmpty()){
            List<Integer> list = new ArrayList<Integer>(); 
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode node = q.remove();
                list.add(node.val);
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
            }
            ((LinkedList)levels).addFirst(list);
        }
        return levels;
    }

X. https://discuss.leetcode.com/topic/36899/java-solution-that-beats-80
http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal-ii/

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    
    List<List<Integer>> counts = new ArrayList<List<Integer>>();
    
    visit(root, counts, 0);
    Collections.reverse(counts);

    return counts;
}

public void visit(TreeNode node, List<List<Integer>> counts, int level){
    if(node == null)
        return;
    if(counts.size() < level+1)
        counts.add(new ArrayList<Integer>());
    counts.get(level).add(node.val);
    
    visit(node.left, counts, level+1);
    visit(node.right, counts, level+1);
}

https://discuss.leetcode.com/topic/44508/java-bfs-and-dfs-solutions

 public List<List<Integer>> levelOrderBottom(TreeNode root) {
     List<List<Integer>> ret = new ArrayList<>();
     Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
     stack.push(new Pair(root, 0));
     while (!stack.isEmpty()) {
         Pair<TreeNode, Integer> p = stack.pop();
         TreeNode node = p.getKey();
         int level = p.getValue();
         if (node != null) {
             if (level == ret.size()) {
                 ret.add(new ArrayList());
             }
             ret.get(level).add(node.val);
             stack.push(new Pair(node.right, level+1));
             stack.push(new Pair(node.left, level+1));
         }
     }
     Collections.reverse(ret);
     return ret;
 }

X. DFS - without reverse results?

X. inefficient
https://discuss.leetcode.com/topic/7651/my-dfs-and-bfs-java-solution
- we need random access
  - list.get(list.size()-level-1).add(root.val);
- we also need add it at first
arraylist, linkedlist are not good here

        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
            levelMaker(wrapList, root, 0);
            return wrapList;
        }
        
        public void levelMaker(List<List<Integer>> list, TreeNode root, int level) {
            if(root == null) return;
            if(level >= list.size()) {
                list.add(0, new LinkedList<Integer>());
            }
            levelMaker(list, root.left, level+1);
            levelMaker(list, root.right, level+1);
            list.get(list.size()-level-1).add(root.val);
        }