public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
Queue<SimpleEntry<TreeNode, Integer>> queue = new LinkedList<>();
queue.offer(new SimpleEntry<>(root, 0));
while(!queue.isEmpty()) {
SimpleEntry<TreeNode, Integer> entry = queue.poll();
TreeNode node = entry.getKey();
int depth = entry.getValue();
//如果这是新的层
if(result.size() == depth) {
List<Integer> list = new ArrayList<Integer>();
list.add(node.val);
result.add(0, list);
}
//如果这是当前层
else {
result.get(0).add(node.val);
}
if(node.left != null) {
queue.offer(new SimpleEntry<TreeNode, Integer>(node.left, depth + 1));
}
if(node.right != null) {
queue.offer(new SimpleEntry<TreeNode, Integer>(node.right, depth + 1));
}
}
return result;
}
本题的关键是把层数和TreeNode绑定在一个SimpleEntry里，让他们有一个对应关系。
利用result.size() == depth判断是否是新的一层，如果是新的一层就new一个ArrayList保存本层的值，并在result[0]插入这个ArrayList，达到逆序的目的。如果不是新的一层，就将result[0]取出，并加本层的值add。
本题是广度优先搜索。
