二叉树按层遍历并收集结点

二叉树按层遍历并收集结点

力扣链接：二叉树的按层遍历II

题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例

提示

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

题解

先不关心倒序的事，这个题目返回的肯定是一个嵌套的list，外层的list套着一个个小list

解题步骤

1. 拿出此时队列的size，size有多少个，步骤2重复多少回；
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);
    }
}

测试结果

代码

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;
    }

扩展

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);

测试结果：插入弹出20000000次，系统栈耗费时间6000多毫秒，自己用数组实现的栈只耗费了79毫秒，极大的优化了常数时间！