题目描述：
/**
* 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.
*
*/就是把二叉树从最下层开是输出，一层一层地向上输出。这样就需要每一层都会存到一个数组里，有n层，那么对于整个二叉树来说，需要声明一个二维的数组才能满足条件。即可以这样声明，ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
最后的结果应该是这样子的：[[15, 7],[9, 20],[3]],每一项都是一层。具体代码如下：
public static ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root){
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
if(root==null)
return ret;
ArrayList<Integer>level = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int currentLevel=1;//遍历的这一层的节点个数
int nextLevel=0;//遍历的下一层的孩子节点个数
while(!queue.isEmpty()){
TreeNode node=queue.remove();//把要遍历的节点弹出队列
level.add(node.val);//leve存储的是这一层的节点
currentLevel--;//每存储一个节点，currentLevel就会少一个
if(node.left!=null){//存储节点的左孩子节点，在这里其实这个节点的兄弟节点已经存储到队列里面去了
queue.add(node.left);
nextLevel++;//记录下一层的节点个数
}
if(node.right!=null)//存储节点的右孩子节点，也相当于存储下一层节点的兄弟节点
{
queue.add(node.right);
nextLevel++;
}
if(currentLevel==0){//如果这一层的节点都存储到level中去了，那么就把level这个数组加入到二维数组。
ret.add(level);
level=new ArrayList<Integer>();
currentLevel=nextLevel;//下一层要遍历的节点个数赋值给currentLevel
nextLevel=0;//下下层的节点个数初始化为0
}
}
int i = 0, j = ret.size() - 1;
while (i < j) {//把得到的二维数组逆置
ArrayList<Integer> tmp = ret.get(i);
ret.set(i, ret.get(j));
ret.set(j, tmp);
i++;
j--;
}
return ret;
}
//测试代码
public static void main(String arg[])
{
TreeNode r1 = new TreeNode(3);
TreeNode r2 = new TreeNode(9);
TreeNode r3 = new TreeNode(20);
TreeNode r4 = new TreeNode(15);
TreeNode r5 = new TreeNode(7);
r1.left = r2;
r1.right = r3;
r2.left=r4;
r3.right=r5;
ArrayList<ArrayList<Integer>> array=levelOrderBottom(r1);
for(int i=0;i<array.size();i++)
{
System.out.print(array.get(i)+",");
}
}遍历的思想是，每遍历一层就把这一层的数据存储到二维数组里，最后把得到的二维数组里的每一项逆置一下就是从下往上遍历的结果了。代码中currentLevel记录的就是这一层的数据，每次当currentLevel为0时，说明这一层的数组已经遍历完了，然后存进二维数组里。nextLevel记录的是下一层节点的个数，在这一层遍历完之后，会把nextLevel的值赋给currentLevel。所以每次往队列queue中存储一个节点currentLevel的值就会减一（currentLevel–）。level数组存储的就是遍历的这一层的数据。每次要遍历的节点都会提前存储到queue队列当中，使用queue的好处就是先进先出，先存储的优先遍历，这样就能保证每次在把第（n+1）层孩子节点存储到queue中时，还能让第(n)层的兄弟节点优先弹出来。