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,null,null,15,7],
3 / \ 9 20 / \ 15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ] ---------- --------------------------------------------------------------------------------------------------------------题意
把一个二叉树自底向上输出。
思路
第一眼看上去开始想怎么用栈去解决，是不是要计算树的深度然后从最大深度的地方开始遍历等等。
其实想得太多，并没有看懂例子理解意思。
代码
public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> wrapList = new LinkedList<List<Integer>>(); if(root == null) return wrapList; queue.offer(root); while(!queue.isEmpty()){ int levelNum = queue.size(); List<Integer> subList = new LinkedList<Integer>(); for(int i=0; i<levelNum; i++) { if(queue.peek().left != null) { queue.offer(queue.peek().left); } if(queue.peek().right != null) { queue.offer(queue.peek().right); } subList.add(queue.poll().val); } wrapList.add(0, subList); } return wrapList; } }方法中利用队列的特点先进先出，自顶向下遍历二叉树，然后利用list的add(args1,args2)方法，将输出的二叉树插入到结果list的最前面，
实现自底向上输出。
另外还有利用递归解决本题的方法
public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null) { return res; } helper(root, 0, res); return res; } public void helper(TreeNode root, int depth, List<List<Integer>> res) { if(root == null) { return; } if(res.size() <= depth) { res.add(0, new ArrayList<Integer>()); } helper(root.left, depth+1, res); helper(root.right, depth+1, res); res.get(res.size() - depth - 1).add(root.val); } }这个采用递归的方法，在每次递归时，深度+1，同时创建list用来后面接受树的值。
