这是我参与11月更文挑战的第5天，活动详情查看：2021最后一次更文挑战
BFS —— 广度优先搜索，咱们在数据结构课一定会学的。一起的还有前、中、后序遍历、DFS（深度优先搜索）， 它们都是二叉树遍历的算法！
实话讲，除了在学校学的时候大概知道这个，后来就陆续忘了......再后来，刷题可能会又捡起来，然后又忘......唉，学了忘，忘了学......
可是，这不就是学习的过程么？So，just do it!
深化复习的最佳限度就是 45 分钟或 9 遍 —— 薛金星
一图胜千言：
如图所示，就是 BFS 的遍历过程，逐层遍历，直至结束；
下面，通过动图具体来看结点进队列和出队列的过程：
直观感受，这和滑动窗口也类似呀，只不过窗口大小随着层级变化而变化；
以 BFS 算法遍历 Dom 树为例，JavaScript 实现：
代码语言：javascript复制function breadthFirstSearch(node) {
var nodes = [];
if (node != null) {
var queue = [];
queue.unshift(node); // 将初始节点放入队中
while (queue.length != 0) {
var item = queue.shift(); // 提取队首元素
nodes.push(item);
var children = item.children;
for (var i = 0; i < children.length; i ) // 遍历全部子元素
queue.push(children[i]); // 推入队中
}
}
return nodes;
}
breadthFirstSearch(document.getElementsByTagName("body")[0])递归实现：
代码语言：javascript复制function breadthFirstSearch(node,nodes) {
if (!(node == null)) {
nodes.push(node);
breadthFirstSearch(node.nextElementSibling,nodes); // 优先遍历兄弟节点
breadthFirstSearch(node.firstElementChild,nodes); // 再遍历子节点
}
return nodes;
}
breadthFirstSearch(document.getElementsByTagName("body")[0],[])递归真好用，来道题吧~
- 二叉搜索树的最近公共祖先
题：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1:
代码语言：javascript复制输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。示例 2:
代码语言：javascript复制输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。注：所有节点的值都是唯一的；p、q 为不同节点且均存在于给定的二叉搜索树中。
解题思路：
- 二叉搜索树特点是，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 基于第 1 点，可得：若 p、q 都小于根节点，则在左子树上；若 p、q 都大于根节点，则都在右子树上；若一大一小，则最近公共祖先节点就是根节点；
JavaScript 递归实现：
代码语言：javascript复制const lowestCommonAncestor = (root, p, q) => {
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
};看完本篇，两个要点：
- BFS，是一种利用队列实现的搜索算法。（与之相对的 DFS 是用栈来处理）
- 在二叉树中遍历、搜素，用递归，很清晰；
我是掘金安东尼，公众号同名，输出暴露输入，技术洞见生活，下次再会~~
