版权声明：本文为博主原创文章，未经博主允许不得转载。
难度：中等
要求：
给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）
样例:
一个例子：
给出一棵二叉树 {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
按照从下往上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
实现：
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/*
* @param root: A tree
* @return: buttom-up level order a list of lists of integer
*/
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
List<Integer> cell = new ArrayList<Integer>();
TreeNode last = root;
TreeNode nLast = root;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.pop();
cell.add(node.val);
if (node.left != null) {
queue.add(node.left);
nLast = node.left;
}
if (node.right != null) {
queue.add(node.right);
nLast = node.right;
}
//换行
if (node == last) {
last = nLast;
ret.add(0, cell);
cell = new ArrayList<Integer>();
}
}
return ret;
}
}
