11.二叉树习题

102. 二叉树的层序遍历

在每一层遍历开始前，先记录队列中的结点数量 nn（也就是这一层的结点数量），然后一口气处理完这一层的 n个结点。
最牛B的在于一开始要先计算出来队列的长度: int n=queue.size();
空间复杂度:节点最多不超过n个，最多的为最后一层的叶子节点n/2，故空间复杂度为O(n)
时间复杂度:每个节点进出各一次，所以总体的时间复杂度为O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
         Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //一开始预先去queue的大小,后面再加元素也就不用担心了！！！
            int n=queue.size();
            List<Integer> innerList=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                innerList.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            list.add(innerList);
        }
        return list;
    }
}