前言

二元樹的層級搜索，指的是從層級由根往葉，以橫的方向逐一遍歷每層節點。
這在圖論中，有個專有的搜尋法：廣度優先搜尋法，Breadth-First Search，就是在講這個模式，我們在聊佇列的時候也有提到，佇列就能用在這上面。

Binary Tree Level Order Traversal

這題給我們一個根節點，並要我們以層級優先的方式做遍歷、把每個層級存在同一個 List 裡，最後用一個 List 把這些 List 裝在裡面，然後回傳這個按層級遍歷的 List。

我們常常會用到佇列來輔助處理層級遍歷，因為依照先進先出的特性，只要放入的順序如同層級順序，那後面就按順序排出，就會是按層級遍歷了。
操作上是這樣的：我們先檢查根節點為不為空，不為空就把根結點放入佇列中。
再來的迴圈終止條件會是佇列為空則終止，迴圈裡會做的事情是：持續提出在佇列中的第一個節點，檢查它的左右子節點為不為空，不為空則放入佇列。這邊可以想像一下，按照這個方式，是不是就正好會按層級的方式、讓節點進入佇列？按照這個方式，最後就會層級遍歷完整個樹結構。

如果單純這樣會少顧到這題要我們「按層級儲存數直到 List 中」，我們怎麼知道什麼時候遍歷完了一層？那就是在進入迴圈後，最開始先取一次佇列大小並記錄，再做第二個迴圈，這個迴圈的終止條件是紀錄下來的佇列大小等於 0，每次我們排出一個節點，這個大小就減 1。因為這個大小只在外層迴圈一開始刷新，所以中間我們放子節點的時候大小並不更動，可以知道我們什麼時候遍歷完一層，同時，放入的這些子節點都同屬一層，會在下次外部迴圈檢查時再重新記錄下這層有多少個節點。如此一來，我們可以在內層迴圈結束的位置，補上我們要對同一層節點做的操作，再讓他進入下一個迴圈。

程式碼如下：

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var queue = new Queue<TreeNode>();
        if(root == null){
            return result;
        }
        queue.Enqueue(root);
        while(queue.Count > 0){
            var size = queue.Count;
            var list = new List<int>();
            while(size > 0){
                var node = queue.Dequeue();
                list.Add(node.val);
                if(node.left != null){
                    queue.Enqueue(node.left);
                }
                if(node.right != null){
                    queue.Enqueue(node.right);
                }
                size--;
            }
            result.Add(list);
        }
        return result;
    }
}

這邊巧妙地運用了佇列的特性，讓我們不必去在意節點的位置，透過放入的順序與先進先出，讓我們可以由上而下、由左而右的層級去遍栗樹的結構，這樣的層級遍歷幾乎是一個模板，只要遇到樹的層級遍歷，那類似這樣的程式碼就可能會出現。

Binary Tree Right Side View

這題給了一個樹的根節點，要求我們回傳一個陣列，裡面是每層最右邊的節點的值。
看到依層相關，就要優先想到層序遍歷，這題的程式碼其實和上題幾乎一樣，如果可以，建議大家先自己練一遍，這題的解釋我會放在程式碼的下面。

public class Solution {
    public IList<int> RightSideView(TreeNode root) {
        var list = new List<int>();
        var queue = new Queue<TreeNode>();
        if(root == null){
            return list;
        }
        queue.Enqueue(root);
        TreeNode node = new TreeNode(-1);
        while(queue.Count > 0){
            var size = queue.Count;
            while(size > 0){
                node = queue.Dequeue();
                if(node.left != null){
                    queue.Enqueue(node.left);
                }
                if(node.right != null){
                    queue.Enqueue(node.right);
                }
                size--;
            }
            list.Add(node.val);
        }
        return list;
    }
}

稍微比對一下，實際這題跟上題的程式碼幾乎一樣，只差在上題做的是每個節點放入 List，並在每層結束的時候把該 List 放到大 List 裡。這題只要最右邊的節點，也就是我們在層序遍歷完，node 變數還保有該層最後一個節點的值的時候，把該節點的值放入 List 裡就好。

大部分層序遍歷的題目只要掌握基本的遍歷模式，因為遍歷模式不變，就只差在遍歷的途中、之前或之後要做的事情，刷類似的題目多刷幾題這種重複感會很強烈，讓你會迅速地掌握這種寫法。

Minimum Depth of Binary Tree

給定一個根結點，要求回傳該棵樹的最小深度，深度定義上根節點為 1，無根節點為 0，要找最小深度的定義是無左右子節點中最上方層級的節點。
看到層級，我們就知道我們可以用層級遍歷來處理，而且寫這類題目也可以想一下，有沒有需要遍歷完整棵樹，還是只要遍歷到一個條件符合，我們就能回傳？
以這題最小這個條件，因為我們是用層級遍歷，由上面層級到下面層級，所以一旦我們找到任何一個節點符合沒有左右子節點，就可以回傳。
邏輯上就是很簡單的使用層級遍歷，然後遍歷到節點時確認該節點有沒有左右子樹，沒有就回傳答案。

public class Solution {
    public int MinDepth(TreeNode root) {
        var depth = 0;
        if(root == null){
            return depth;
        }
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while(queue.Count > 0){
            var size = queue.Count;
            depth++;
            while(size > 0){
                var node = queue.Dequeue();
                if(node.left != null){
                    queue.Enqueue(node.left);
                }
                if(node.right != null){
                    queue.Enqueue(node.right);
                }
                if(node.left == null && node.right == null){
                    return depth;
                }
                size --;
            }
        }
        throw new Exception();
    }
}

有一個我建議大家想清楚的是，在寫這類題目，迴圈外實際上不會到達的地方，要給回一個值，還是拋出例外，我會建議拋出例外，明確知道該處是不可能到達的。特異值也是一個方法，但例外會比特異值更醒目，能明確指出若程式碼運行到這個地方，一定是哪裡出了問題(輸入資料、敘述邏輯)。
以這題為例，可以想見任何一棵樹一定會在某棵節點時遇到左右子節點為空的情況，否則該棵樹就是一棵無限大的樹了，所以要遍歷完整棵樹但沒有任何節點是沒有左右子節點的，這個情況是不可能發生的，於是我在迴圈外寫了一個拋出例外，因為 Leetcode 的程式碼惠要求所有地方都有回傳，或是拋出例外，這邊我拋出例外來彰示這裡是不會到達的。

層級遍歷的邏輯我想透過接連三題，應該是很明白了，當題目的問題核心與層級相關，層級遍歷就可以套套看。同時，層級遍歷也能夠完整遍歷完整棵樹，如果前中後序，三序想不通套不上，也可以試試層級遍歷，也許會有不同的結果。