二叉树层序遍历总结

什么是层序遍历？

我概括为：就是一层一层的遍历二叉树。很显然，如果要实现这个功能，用队列来实现很合适，我们都知道队列是先进先出的，层序遍历就是把这一层的按顺序进来，又按顺序出去。但是，遍历顺序只能从根节点向下遍历，因为队列得依靠二叉树的连接关系，从后往前连接关系就断了。

层序遍历的模版

1. 将根节点加入到队列中
2. 会做两个判断，第一个对整个树来说的，第二个判断则是对当前层来说。第一个条件为队列不为空，因为一旦为空了，则说明都遍历完了。第二个判断当前层有没有遍历完，因此要保留一下长度。
3. 将当前层的节点添加到列表中，可以顺序也可以逆序。

List<Integer> res = new LinkedList<>();
Deque<TreeNode> queue = new LinkedList<>();
if(root == null){
    return res;
}
queue.offer(root);
while(!queue.isEmpty()){
    // 这里是对每一层节点的处理
    List<Integer> list = new LinkedList<>();
    int size = queue.size(); // 保留该层的应该遍历的节点数，因为还有其他层的
    for(int i =0;i<size;i++){
        TreeNode node = queue.poll();
        list.add(node.val);
        if(node.left!=null){
            queue.offer(node.left);
        }
        if(node.right!=null){
            queue.offer(node.right);
        }
    }
    res.add(list.getLast());
}

使用场景

• 打印树的结构
• bfs
• 二叉树的最小/最大深度：最小深度就返回左右节点都为空，最大就正常
• 判断平衡二叉树：判断每一层的节点个数
• 树的序列化

时间复杂度和空间复杂度

1. 时间复杂度：

   • 层序遍历需要访问二叉树中的每个节点恰好一次。因此，如果二叉树中有 ( n ) 个节点，时间复杂度为 ( O(n) )。

2. 空间复杂度：

   • 层序遍历通常使用队列来实现，队列中存储的是每一层的节点。在最坏的情况下，队列中可能存储了二叉树最底层的所有节点。对于一个完全二叉树，最底层的节点数大约是 ( n/2 )（其中 ( n ) 是总节点数）。因此，空间复杂度为 ( O(n) )。