好的，BFS，学会了
BFS —— 广度优先搜索，咱们在数据结构课一定会学的。一起的还有前、中、后序遍历、DFS（深度优先搜索）， 它们都是二叉树遍历的算法！
实话讲，除了在学校学的时候大概知道这个，后来就陆续忘了......再后来，刷题可能会又捡起来，然后又忘......唉，学了忘，忘了学......
可是，这不就是学习的过程么？So，just do it!
深化复习的最佳限度就是 45 分钟或 9 遍 —— 薛金星
一图胜千言：
如图所示，就是 BFS 的遍历过程，逐层遍历，直至结束；
下面，通过动图具体来看结点进队列和出队列的过程：
直观感受，这和滑动窗口也类似呀，只不过窗口大小随着层级变化而变化；
以 BFS 算法遍历 Dom 树为例，JavaScript 实现：
递归实现：
递归真好用，来道题吧~
题：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1:
示例 2:
注：所有节点的值都是唯一的；p、q 为不同节点且均存在于给定的二叉搜索树中。
解题思路：
二叉搜索树特点是，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
基于第 1 点，可得：若 p、q 都小于根节点，则在左子树上；若 p、q 都大于根节点，则都在右子树上；若一大一小，则最近公共祖先节点就是根节点；
JavaScript 递归实现：
<hr>
看完本篇，两个要点：
BFS，是一种利用队列实现的搜索算法。（与之相对的 DFS 是用栈来处理）
在二叉树中遍历、搜素，用递归，很清晰；
我是掘金安东尼，公众号同名，输出暴露输入，技术洞见生活，下次再会~~
版权声明: 本文为 InfoQ 作者【掘金安东尼】的原创文章。
原文链接:【http://xie.infoq.cn/article/3645f69621e430952ddb853dd】。文章转载请联系作者。
安东尼陪你度过漫长编程岁月~ 2022.07.14 加入
真正的大师，永远怀着一颗学徒的心（易）
评论