本文概览本文以LeetCode题目二叉树的层序遍历为例详细讲解BFS广度优先搜索的原理和实现重点说明为什么用队列、队列如何保证层序、以及如何按层分组输出一、题目二、题目分析题目要求按层从上到下、从左到右遍历二叉树每一层的节点值放在一个列表中最终返回一个列表的列表比如3 / \ 9 20 / \ 15 7 输出[[3], [9, 20], [15, 7]]这道题的核心就是BFS广度优先搜索也叫层序遍历。和之前用递归DFS“一根筋往下钻不同BFS 是一层一层扫”思路概览Java 实现代码如下publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresnewArrayList();if(rootnull){returnres;}QueueTreeNodequeuenewLinkedList();// 根节点入队queue.offer(root);while(!queue.isEmpty()){// 当前层的节点数intsizequeue.size();ListIntegerlistnewArrayList();// 逐个处理当前层的节点for(inti0;isize;i){TreeNodenodequeue.poll();list.add(node.val);// 左孩子入队if(node.left!null){queue.offer(node.left);}// 右孩子入队if(node.right!null){queue.offer(node.right);}}res.add(list);}returnres;}思路简要说明用队列来控制遍历顺序先进先出保证从左到右每轮开始前记录队列大小size这就是当前层的节点数逐个出队当前层的节点把值加入结果同时把左右孩子依次入队一轮结束当前层处理完毕队列里剩下的是下一层的节点三、思路详解DFS vs BFS两种遍历思路先回顾一下中序遍历DFS它的遍历路径是一根筋往下钻3 / \ 9 20 / \ 15 7 中序遍历DFS9 → 3 → 15 → 20 → 7 先一条路走到黑9再回退再走到黑15再回退... 深度优先纵向展开而层序遍历BFS是一层一层扫3 / \ 9 20 / \ 15 7 层序遍历BFS[3] → [9, 20] → [15, 7] 先扫第一层再扫第二层再扫第三层... 广度优先横向展开DFS 是先往深处走BFS 是先往宽处走。DFS 靠递归实现BFS 靠队列实现为什么用队列BFS 的核心数据结构是队列Queue。队列的特性是先进先出FIFO这正好满足按层顺序处理的需求想一想要按层遍历就必须先处理上层的节点再处理下层的节点。队列的先进先出保证了当前层的节点先入队所以先出队孩子节点后入队所以等当前层都出完了下一层才轮到出队用一个形象的比喻队列就像一条排队的通道。当前层的人在前面处理处理完一个就把他的孩子下一层的节点排到队伍末尾。等前面这一批人都处理完了下一批人自然就排到了队伍前面整个流程可以概括为一句话把当前层的节点依次出队出队的同时把它们的孩子依次入队怎么按层分组题目要求每一层的节点放在一个单独的列表中所以关键问题是怎么区分哪些节点属于同一层答案在于每轮开始前队列里恰好只有当前层的节点为什么因为上一轮出队时把当前层的节点都出完了只留下了它们的孩子们即下一层的节点。所以每轮开始时queue.size()就是当前层的节点数这个size非常关键——它告诉我们这轮要出队几个节点。用 for 循环精确地出队size个节点就不会多出下一层的节点size必须在 for 循环外记录。如果放在循环条件里用queue.size()因为循环中会往队列加入新节点孩子大小会不断变化导致一轮处理了多层的节点图解完整过程3 / \ 9 20 / \ 15 7初始队列 [3]第 1 轮处理第 1 层当前队列大小 1说明第 1 层有 1 个节点队列[3] 出队 3 → 加入结果 [3] 3 有左孩子 9 → 入队 3 有右孩子 20 → 入队 队列变为[9, 20]第 2 轮处理第 2 层当前队列大小 2说明第 2 层有 2 个节点队列[9, 20] 出队 9 → 加入结果 [3, 9] 9 没有左孩子 9 没有右孩子 队列变为[20] 出队 20 → 加入结果 [3, 9, 20] 20 有左孩子 15 → 入队 20 有右孩子 7 → 入队 队列变为[15, 7]第 3 轮处理第 3 层当前队列大小 2说明第 3 层有 2 个节点队列[15, 7] 出队 15 → 加入结果 [3, 9, 20, 15] 15 没有左孩子 15 没有右孩子 队列变为[7] 出队 7 → 加入结果 [3, 9, 20, 15, 7] 7 没有左孩子 7 没有右孩子 队列变为[]空队列空了遍历结束。最终结果按层分组[[3], [9, 20], [15, 7]]可以看到每一轮开始时队列中恰好是当前层的所有节点。这是因为上一轮出队当前层节点的同时把它们的孩子下一层节点入队了。等当前层全部出队完毕队列里就只剩下下一层的节点入队顺序先左后右题目要求从左到右遍历所以入队顺序必须是先左孩子后右孩子。因为队列是先进先出的先入队的先出队所以先入队左孩子就能保证同一层中左边的节点先被处理如果先入队右孩子再入队左孩子同一层的节点就会变成从右到左的顺序不符合题目要求复杂度分析时间复杂度O(n)每个节点恰好入队一次、出队一次空间复杂度O(n)队列中最多同时存放一层节点最坏情况完全二叉树最后一层约为 n/2 个节点
本文概览本文以LeetCode题目二叉树的层序遍历为例详细讲解BFS广度优先搜索的原理和实现重点说明为什么用队列、队列如何保证层序、以及如何按层分组输出一、题目二、题目分析题目要求按层从上到下、从左到右遍历二叉树每一层的节点值放在一个列表中最终返回一个列表的列表比如3 / \ 9 20 / \ 15 7 输出[[3], [9, 20], [15, 7]]这道题的核心就是BFS广度优先搜索也叫层序遍历。和之前用递归DFS“一根筋往下钻不同BFS 是一层一层扫”思路概览Java 实现代码如下publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresnewArrayList();if(rootnull){returnres;}QueueTreeNodequeuenewLinkedList();// 根节点入队queue.offer(root);while(!queue.isEmpty()){// 当前层的节点数intsizequeue.size();ListIntegerlistnewArrayList();// 逐个处理当前层的节点for(inti0;isize;i){TreeNodenodequeue.poll();list.add(node.val);// 左孩子入队if(node.left!null){queue.offer(node.left);}// 右孩子入队if(node.right!null){queue.offer(node.right);}}res.add(list);}returnres;}思路简要说明用队列来控制遍历顺序先进先出保证从左到右每轮开始前记录队列大小size这就是当前层的节点数逐个出队当前层的节点把值加入结果同时把左右孩子依次入队一轮结束当前层处理完毕队列里剩下的是下一层的节点三、思路详解DFS vs BFS两种遍历思路先回顾一下中序遍历DFS它的遍历路径是一根筋往下钻3 / \ 9 20 / \ 15 7 中序遍历DFS9 → 3 → 15 → 20 → 7 先一条路走到黑9再回退再走到黑15再回退... 深度优先纵向展开而层序遍历BFS是一层一层扫3 / \ 9 20 / \ 15 7 层序遍历BFS[3] → [9, 20] → [15, 7] 先扫第一层再扫第二层再扫第三层... 广度优先横向展开DFS 是先往深处走BFS 是先往宽处走。DFS 靠递归实现BFS 靠队列实现为什么用队列BFS 的核心数据结构是队列Queue。队列的特性是先进先出FIFO这正好满足按层顺序处理的需求想一想要按层遍历就必须先处理上层的节点再处理下层的节点。队列的先进先出保证了当前层的节点先入队所以先出队孩子节点后入队所以等当前层都出完了下一层才轮到出队用一个形象的比喻队列就像一条排队的通道。当前层的人在前面处理处理完一个就把他的孩子下一层的节点排到队伍末尾。等前面这一批人都处理完了下一批人自然就排到了队伍前面整个流程可以概括为一句话把当前层的节点依次出队出队的同时把它们的孩子依次入队怎么按层分组题目要求每一层的节点放在一个单独的列表中所以关键问题是怎么区分哪些节点属于同一层答案在于每轮开始前队列里恰好只有当前层的节点为什么因为上一轮出队时把当前层的节点都出完了只留下了它们的孩子们即下一层的节点。所以每轮开始时queue.size()就是当前层的节点数这个size非常关键——它告诉我们这轮要出队几个节点。用 for 循环精确地出队size个节点就不会多出下一层的节点size必须在 for 循环外记录。如果放在循环条件里用queue.size()因为循环中会往队列加入新节点孩子大小会不断变化导致一轮处理了多层的节点图解完整过程3 / \ 9 20 / \ 15 7初始队列 [3]第 1 轮处理第 1 层当前队列大小 1说明第 1 层有 1 个节点队列[3] 出队 3 → 加入结果 [3] 3 有左孩子 9 → 入队 3 有右孩子 20 → 入队 队列变为[9, 20]第 2 轮处理第 2 层当前队列大小 2说明第 2 层有 2 个节点队列[9, 20] 出队 9 → 加入结果 [3, 9] 9 没有左孩子 9 没有右孩子 队列变为[20] 出队 20 → 加入结果 [3, 9, 20] 20 有左孩子 15 → 入队 20 有右孩子 7 → 入队 队列变为[15, 7]第 3 轮处理第 3 层当前队列大小 2说明第 3 层有 2 个节点队列[15, 7] 出队 15 → 加入结果 [3, 9, 20, 15] 15 没有左孩子 15 没有右孩子 队列变为[7] 出队 7 → 加入结果 [3, 9, 20, 15, 7] 7 没有左孩子 7 没有右孩子 队列变为[]空队列空了遍历结束。最终结果按层分组[[3], [9, 20], [15, 7]]可以看到每一轮开始时队列中恰好是当前层的所有节点。这是因为上一轮出队当前层节点的同时把它们的孩子下一层节点入队了。等当前层全部出队完毕队列里就只剩下下一层的节点入队顺序先左后右题目要求从左到右遍历所以入队顺序必须是先左孩子后右孩子。因为队列是先进先出的先入队的先出队所以先入队左孩子就能保证同一层中左边的节点先被处理如果先入队右孩子再入队左孩子同一层的节点就会变成从右到左的顺序不符合题目要求复杂度分析时间复杂度O(n)每个节点恰好入队一次、出队一次空间复杂度O(n)队列中最多同时存放一层节点最坏情况完全二叉树最后一层约为 n/2 个节点
