BFS —— 广度优先搜索，咱们在数据结构课一定会学的。一起的还有前、中、后序遍历、DFS（深度优先搜索）， 它们都是二叉树遍历的算法！
实话讲，除了在学校学的时候大概知道这个，后来就陆续忘了......再后来，刷题可能会又捡起来，然后又忘......唉，学了忘，忘了学......
可是，这不就是学习的过程么？So，just do it!
深化复习的最佳限度就是 45 分钟或 9 遍 —— 薛金星
一图胜千言：
如图所示，就是 BFS 的遍历过程，逐层遍历，直至结束；
下面，通过动图具体来看结点进队列和出队列的过程：
直观感受，这和滑动窗口也类似呀，只不过窗口大小随着层级变化而变化；
以 BFS 算法遍历 Dom 树为例，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])
递归实现：
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:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: 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 递归实现：
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 是用栈来处理）
- 在二叉树中遍历、搜素，用递归，很清晰；
我是掘金安东尼，公众号同名，输出暴露输入，技术洞见生活，下次再会~
