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

Java

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        List<Integer> items = new ArrayList<Integer>();
        LinkedList<TreeNode> cur = new LinkedList<TreeNode>();
        LinkedList<TreeNode> nxt = new LinkedList<TreeNode>();

        if(root == null) {
            return rst;
        } else {
            cur.add(root);
        }

        while(!cur.isEmpty()) {
            TreeNode now = cur.poll();
            items.add(now.val);
            if(now.left != null) {
                nxt.add(now.left);
            }
            if(now.right != null) {
                nxt.add(now.right);
            }

            if(cur.isEmpty()) {
                cur.addAll(nxt);
                rst.add(new ArrayList(items));
                nxt.clear();
                items.clear();
            }
        }

        Collections.reverse(rst);
        return rst;
    }
}