好的，BFS，又学废了！

掘金安东尼

发布于 2022-09-19 11:03:29

2030

发布于 2022-09-19 11:03:29

文章被收录于专栏：掘金安东尼

这是我参与11月更文挑战的第5天，活动详情查看：2021最后一次更文挑战

BFS —— 广度优先搜索，咱们在数据结构课一定会学的。一起的还有前、中、后序遍历、DFS（深度优先搜索），它们都是二叉树遍历的算法！

实话讲，除了在学校学的时候大概知道这个，后来就陆续忘了......再后来，刷题可能会又捡起来，然后又忘......唉，学了忘，忘了学......

可是，这不就是学习的过程么？So，just do it!

深化复习的最佳限度就是 45 分钟或 9 遍 —— 薛金星

一图胜千言：

如图所示，就是 BFS 的遍历过程，逐层遍历，直至结束；

下面，通过动图具体来看结点进队列和出队列的过程：

4529bf559c6a2d84d550eebaee027c3b7ae25069e4ec91f27b29a4c6358d6662.gif

直观感受，这和滑动窗口也类似呀，只不过窗口大小随着层级变化而变化；

以 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 &amp;&amp; q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    if (p.val > root.val &amp;&amp; q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
};

看完本篇，两个要点：