LeetCode中廣度優(yōu)先搜索算法的示例分析

一、認(rèn)識廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(BFS)算法是圖的一種遍歷方法，它的核心思想是從圖的某一個(gè)節(jié)點(diǎn)開始，依次遍歷相鄰節(jié)點(diǎn)，再從這些相鄰節(jié)點(diǎn)繼續(xù)向外層節(jié)點(diǎn)遍歷，直到連通圖的所有節(jié)點(diǎn)均被訪問到。

如上圖所示，A、B、C、D、E、F六個(gè)節(jié)點(diǎn)構(gòu)成了連通圖。我們使用廣度優(yōu)先搜索算法對該連通圖進(jìn)行遍歷，從A點(diǎn)出發(fā)，找到A點(diǎn)的相鄰節(jié)點(diǎn)B點(diǎn)和F點(diǎn)，再分別找到B點(diǎn)和F點(diǎn)的相鄰節(jié)點(diǎn)C點(diǎn)和E點(diǎn)，最終找到C點(diǎn)和E點(diǎn)的共同相鄰節(jié)點(diǎn)D點(diǎn)。因此我們得到的遍歷結(jié)果為ABFCED。

二、Leetcode常見廣度優(yōu)先搜索形式

當(dāng)我們打開Leetcode的廣度優(yōu)先搜索標(biāo)簽，查看相關(guān)算法題時(shí)會發(fā)現(xiàn)，很多題是將連通圖簡化為樹或二叉樹的形式展示。因此我們可以從樹/二叉樹的角度分析廣度優(yōu)先搜索算法，只要搞懂了樹的廣度優(yōu)先搜索，圖的廣度優(yōu)先搜索只是相鄰節(jié)點(diǎn)的選擇差異罷了。
廣度優(yōu)先搜索算法在樹/二叉樹中被簡化為層次遍歷算法，即從樹的根節(jié)點(diǎn)出發(fā)，依次遍歷根節(jié)點(diǎn)的孩子，再分別將這些孩子作為根節(jié)點(diǎn)，循環(huán)上述操作，直至將所有的節(jié)點(diǎn)全部遍歷結(jié)束。
如下圖所示，樹的層次遍歷就是一種特殊的廣度優(yōu)先搜索。根據(jù)上文的遍歷規(guī)則不難得出樹的廣度優(yōu)先搜索序列為ABCDEFG。

三、一道算法題講解具體的BFS實(shí)現(xiàn)思路

我選取了Leetcode上一道典型的廣度優(yōu)先搜索算法給大家整理一下BFS的算法基本實(shí)現(xiàn)思路，題目如下：

思路: 從題意中我們不難看出，該題的核心問題就是求出二叉樹的每一層中最右邊的節(jié)點(diǎn)的值并將其存入數(shù)組最后返回該數(shù)組。很顯然，利用廣度優(yōu)先搜索算法可以很容易將每一層的最右節(jié)點(diǎn)求出。
對于廣度優(yōu)先搜索算法，我們需要申請一個(gè)輔助隊(duì)列幫助我們存儲每一層的每一個(gè)節(jié)點(diǎn)。首先需要對根節(jié)點(diǎn)判空，若根節(jié)點(diǎn)為空則直接返回一個(gè)空數(shù)組，否則將根節(jié)點(diǎn)存入隊(duì)列中。接下來我們需要將隊(duì)列中該層的所有節(jié)點(diǎn)取出，并找出它們的孩子節(jié)點(diǎn)存入隊(duì)列中。需要注意的是，到了最右節(jié)點(diǎn)時(shí)應(yīng)將該節(jié)點(diǎn)的值存入數(shù)組。循環(huán)該過程直至遍歷二叉樹的所有節(jié)點(diǎn)即可得出最終的結(jié)果。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            TreeNode currentNode = null;
            while (count > 0) {
                count--;
                currentNode = queue.poll();
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
            ans.add(currentNode.val);
        }
        return ans;
    }
}

算法復(fù)雜度分析：算法需要訪問該二叉樹中的每個(gè)節(jié)點(diǎn)并且每個(gè)節(jié)點(diǎn)的訪問時(shí)間為O(1)，所以最終的事件復(fù)雜度為O(n)。對于空間復(fù)雜度，我們申請了一個(gè)輔助隊(duì)列幫助存儲二叉樹節(jié)點(diǎn)，最終的空間復(fù)雜度也可表示為O(n)。