给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）
在线评测地址：领扣题库官网
例1:
输入:
{1,2,3}
输出:
[[2,3],[1]]
解释:
1
/ \
2 3
它将被序列化为 {1,2,3}
层次遍历例2:
输入:
{3,9,20,#,#,15,7}
输出:
[[15,7],[9,20],[3]]
解释:
3
/ \
9 20
/ \
15 7
它将被序列化为 {3,9,20,#,#,15,7}
层次遍历算法：二叉树的层次遍历
层次遍历，可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历，开辟一个新队列，让头结点入队并计算此时的长度，每次都将一层的所有节点压入队列后，得到队列的大小，然后将这这一层的所有点都进行遍历，将从左到右每一个点的子节点都压入队列，将本层节点遍历完后，继续下一层的遍历，然后开始循环，一直遍历到底层，判断的终止条件就是队列为空。
- 循环里面，队列头出队，判断其是否有左右子结点，如果有，则入队，但此时还不需要更新队列的长度，当前队列的长度是每层的长度。当这层的长度减为0时，就说明这层的遍历结束，开始更新长度为下一层的长度。
- 出队的元素的值按照一层层压入结果数组
- 因为题目要求自底向上，那么我们不移动每一层的内容，对层进行倒序
复杂度分析
-
时间复杂度O(n)
- n为树的节点数
-
空间复杂度O(n)
- 保存节点位置 n为树的节点数
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) {
// write your code here
List<List<Integer>> ans = new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.offer(root);
}
//层次遍历
while (!queue.isEmpty()) {
int len = queue.size();
List<Integer> tmpList = new ArrayList<>();
while (len > 0) {
TreeNode treeNode = queue.poll();
tmpList.add(treeNode.val);
if (treeNode.left != null) { //左子树不为空的话压入队列
queue.offer(treeNode.left);
}
if (treeNode.right != null) {//右子树不为空的话压入队列
queue.offer(treeNode.right);
}
len--;
}
ans.add(tmpList);//储存当前层的节点
}
//倒序
Collections.reverse(ans);
return ans;
}
}更多题解参考：九章官网solution
