我們一般都求二元樹的最大深度，不過我們今天的練習改成使用BFS來尋找其中的最小高度．

題目是這樣的，給你一個二元樹，求其中最小高度，也就是根節點到葉節點最短的距離．

怎麼套入BFS框架呢？首先我們來確定一下起點跟終點是如何定義的．

根據題目，起點就是我們開始遍歷樹的根節點，終點就是最靠近根節點的葉節點，而要怎麼判斷葉節點就是看左右子節點都是空的節點

把這些訊息帶入昨天講到的BFS演算法架構，可以寫成這樣

fun minDepth(rootNode: TreeNode?): Int {
    if (rootNode == null) {//傳了空的根節點進來
        return 0
    }
    val queue: Queue<TreeNode> = LinkedList()
    queue.offer(rootNode)
    var depth = 1 //跟節點也算一層 所以從1開始

    while (queue.isNotEmpty()) {
        val size = queue.size
        println("queue size: $size")
        //將目前放在Queue中的所有節點往外擴散 向外尋找
        for (i in 0 until size) {
            val currentNode = queue.poll()

            if(currentNode!=null){
                println("current node ${currentNode.value}")
                if (currentNode.left == null && currentNode.right == null) {
                    //判斷是不是到達葉節點
                    println("final node ${currentNode.value}")
                    return depth
                }
                if(currentNode.left!=null){//將相鄰的節點加入Queue中
                    queue.offer(currentNode.left)
                }
                if(currentNode.right!=null){//將相鄰的節點加入Queue中
                    queue.offer(currentNode.right)
                }
            }
        }
        depth++//在這裡增加一步 代表要往下一層
    }
    return 0
}

我們拿一個簡單的樹來測試看看 資料是“8 9 1 3 2 5 7 6 4 10”

畫成樹如下，可以明顯看出來最矮高度為3

讓我們來測試一下這段程式碼的結果

如何建立這個樹就麻煩大家自己動手了．
大概理解BFS的運作邏輯後，我們來看看這兩個問題

為什麼BFS可以找到最短路徑，DFS做不到嗎？

DFS找不到最短路徑嗎?其實也是可以，並且時間複雜度等級也同樣是O(N)，但是實際上的效率低上BFS不少．

觀察一下上面的程式執行結果圖，可以看到BFS是一層一層地往下遍歷，可以把它想像成一次前進一層

把剛剛的樹圖劃上紅線之後就很明顯了，BFS一次前進一層，如果找到了答案，就不會繼續執行．所以在節點10的地方就回傳答案，不再浪費．

而DFS，靠著是遞迴的堆疊紀錄走過的路徑，如果要找到其中最短的．就要走完整棵樹，再從其中比較路徑，找出最短的．

既然BFS這麼好，我們要DFS幹什麼？

BFS雖然可以輕鬆找到最短距離，但是空間複雜度比DFS高．如果題目有要求空間複雜度的時候，可能就不能使用．

同樣舉二元樹來當例子，假設這個二元樹是一個滿二元樹，也就是除了葉節點外，‘每個節點都有兩個子節點．對於DFS來說，空間複雜度就是遞迴的堆疊，在最糟糕的情況，空間複雜度就是樹的高度 ，也就是O(logN)．但是BFS每次都會儲存樹一整層的所有節點，所以在最糟糕的情況，空間複雜度就是樹最下層節點的數目，表示起來就是O(N)

所以BFS也不是完完全全贏過DFS的，一般來說我們在題目找尋最短路徑時使用BFS，而其他題目還是用DFS比較多一點，主要是比較好寫．
根據題目選擇演算法是技巧之一．

明天我們會利用BFS再來挑戰難一點的題目，在最少次數中解開密碼鎖．