二叉树按层遍历并收集结点
力扣链接：二叉树的按层遍历II
题目
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例
提示
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
题解
先不关心倒序的事，这个题目返回的肯定是一个嵌套的list，外层的list套着一个个小list
解题步骤
- 拿出此时队列的size，size有多少个，步骤2重复多少回；
- 弹出当前结点，当前结点有左孩子就先将左孩子加入队列，有右孩子再将右孩子加入队列；（先左再右）
问题
经历上面的步骤，确实是按顺序收集好了，但是题目要求的是倒序收集，即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历
此时如果外层的list用的是ArrayList的话，因为它底层就是数组，所以插入数据代价是O(N)的；如果外层用的是LinkedList，它底层用的是链表，插入数据的代价就是O(1)的。
小测试（分别测试ArrayList和LinkedList插入数据的效率），每次都在0位置上插入数据，测试了300000组，单位时间为毫秒（刚兴趣的同学也可以自己测试下）
public class Code10_BinaryTreeLevelOrderTraversalII {
public static void main(String[] args) {
int testTimes=300000;
long start;
long end;
ArrayList<Integer> arr1=new ArrayList<>();
start=System.currentTimeMillis();
for(int i=0; i<testTimes; i++){
arr1.add(0,i);
}
end=System.currentTimeMillis();
System.out.println(end-start);
LinkedList<Integer> arr2=new LinkedList<>();
start=System.currentTimeMillis();
for(int i=0; i<testTimes; i++){
arr2.add(0,i);
}
end=System.currentTimeMillis();
System.out.println(end-start);
}
}
AI 代码解读
测试结果
代码
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans=new LinkedList<>();
if(root==null){
return ans;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size=queue.size();// 必须要记录size，不能直接 i<queue.size()
List<Integer> curAns=new LinkedList<>();
for(int i=0; i<size; i++){
TreeNode curNode=queue.poll();
curAns.add(curNode.val);
if(curNode.left!=null){
queue.add(curNode.left);
}
if(curNode.right!=null){
queue.add(curNode.right);
}
}
ans.add(0,curAns);
}
return ans;
}
AI 代码解读
扩展
Java中队列是个接口，不能够自己实现。栈可以自己实例化，但是Java中栈的方法实现起来是比较慢的（具体为什么慢就要去看源码了，可以说是个经验），所以如果想优化常数时间的话，应该自己去实现一个栈，而别去用Java系统中提供的栈，可以用LinkedList，也可以用数组（栈不就是先进后出嘛）。
最快的情况下就是用数组实现栈（一些笔试情况下，需要优化常数时间的时候，经常用到），假设数组长度为一万，那么我们也可以确定栈的大小就是一万...
我们也可以来做个小测试
int testTimes2=20000000;
start=System.currentTimeMillis();
Stack<Integer> stack1=new Stack<>();
for(int i=0; i<testTimes2; i++){
stack1.push(i);
}
while(!stack1.isEmpty()){
int a=stack1.pop();
}
end=System.currentTimeMillis();
System.out.println(end-start);
start=System.currentTimeMillis();
int[] stack2=new int[testTimes2];
int i=0;
for( ; i<testTimes2; i++){
stack2[i++]=i;
}
while(i!=0){
int b=stack2[--i];
}
end=System.currentTimeMillis();
System.out.println(end-start);
AI 代码解读
测试结果：插入弹出20000000次，系统栈耗费时间6000多毫秒，自己用数组实现的栈只耗费了79毫秒，极大的优化了常数时间！
