107 Binary Tree Level Order Traversal II

Question:

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]
]

Analysis:

top-bottom traverse, and then reverse it.

Lesson Learned:

• Collections.reverse();

        Collections.reverse(lists);
  

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        Queue<TreeNode> nodes = new LinkedList<TreeNode>();
        TreeNode parent = root;
        if (root == null) {
            return lists;
        }
        nodes.add(parent);

        int count = 0;
        int num = 1;
        while (nodes.peek() != null) {
            lists.add(new ArrayList<Integer>());
            for (int i = 0; i < num; i++) {
                parent = nodes.remove();
                lists.get(lists.size() - 1).add(parent.val);
                if (parent.left != null) {
                    nodes.add(parent.left);
                    count++;
                }
                if (parent.right != null) {
                    nodes.add(parent.right);
                    count++;
                }
            }
            num = count;
            count = 0;
        }
        // Collections.reverse();
        Collections.reverse(lists);
        return lists;
    }
}