在查找二叉樹某個節點時，如果把二叉樹所有節點理理解為解空間，待找到那個節點理解為滿足特定條件的解，對此解答可以抽象描述為： _在解空間中搜索滿足特定條件的解_，這其實就是搜索演算法（Search）的一種描述。當然也有其他描述，比如是“指一類用於在數據集合中查找特定項或解決問題的演算法”，又或者是“指通過... ...
深搜（DFS）與廣搜（BFS）
在查找二叉樹某個節點時，如果把二叉樹所有節點理解為解空間，待找到那個節點理解為滿足特定條件的解，對此解答可以抽象描述為： 在解空間中搜索滿足特定條件的解，這其實就是搜索演算法（Search）的一種描述。當然也有其他描述，比如是“指一類用於在數據集合中查找特定項或解決問題的演算法”，又或者是“指通過按照一定規則逐一檢查數據，以找到所需的信息或解決特定的問題。”等等。
搜索演算法在電腦科學和信息檢索中具有廣泛的應用，包括搜索引擎、資料庫查詢、排序、路徑規劃、機器學習和人工智慧等領域。其中最基礎之一的搜索演算法就是 深度優先搜索（Depth First search，簡稱 DFS）和廣度優先搜索（Breadth First Search，簡稱 BFS）。
PS：因發明“深度優先搜索演算法”，約翰·霍普克洛夫特 與 羅伯特·塔揚在1986年共同獲得電腦領域的最高獎圖靈獎
在寫這兩種演算法之前，先看幾個數據結構。
隊列（Queue）、棧（Stack）
排隊相信是日常生活中購物時可能遇到的情況，其中最重要的一個原則就是先來的先買。同樣的，可以把類似這種規則應用在數據結構上，那麼這種數據結構就是隊列（Queue）：是一種線性數據結構，遵循先進先出（First-In-First-Out，FIFO）的原則。
（PS：什麼叫線性數據？指一種數據元素的有序集合，其中元素之間存線上性（有序）關係。）
其兩個基本的操作：
- 入隊（Enqueue）： 向隊列的末尾添加一個新元素。這個操作將新元素排隊等待被處理。通常，它是隊列中元素的最後一個操作。
- 出隊（Dequeue）： 從隊列的前端移除一個元素，並返回它。這個操作模擬了第一個等待的元素被處理的情況。通常，出隊操作是隊列中元素的第一個操作。
如果把隊列遵循的原則進行修改為後進先出，這樣就演變出另外一種數據結構 棧（Stack）：是一種線性數據結構，它遵循先進後出（Last-In-First-Out，LIFO）的原則。
同樣類似隊列兩個基本操作：
- 入棧（Push）： 向棧頂添加一個新元素。
- 出棧（Pop）： 從棧頂移除元素。
PS：棧頂（Top）是當前位於棧的頂部的元素，也是棧中唯一一個可見的元素。
LeetCode 20. 有效的括弧【簡單】
給定一個只包括 '('，')'，'{'，'}'，''，'' 的字元串 s ，判斷字元串是否有效。
有效字元串需滿足：
- 左括弧必須用相同類型的右括弧閉合。
- 左括弧必須以正確的順序閉合。
- 每個右括弧都有一個對應的相同類型的左括弧。
雙端隊列（Double-Ended Queue，簡稱 Deque）
如果要一個數據結構即支持隊列的操作也支持棧的操作，雙端隊列（Double-Ended Queue，簡稱Deque）是這樣一種線性數據結構，它具有隊列和棧的特性，允許在隊列的兩端執行插入和刪除操作。雙端隊列支持元素的快速插入和刪除，無論是在隊列的前端（頭部）還是後端（尾部），因此它被稱為"雙端"，即有兩個端點。
雙端隊列的存儲實現上既可以 是鏈表，也可以是 數組；可以根據實際情況進行選擇。
// java 示例代碼
Deque<Integer> dequeList = new LinkedList<>();
Deque<Integer> dequeArray = new ArrayDeque<>();
PS：由於雙端隊列能夠覆蓋 棧、隊列兩者的操作，使用Java解決演算法題時，如需使用棧（Stack）、隊列（Queue）情況 經常都會使用 Deque 來完成。
深度優先搜索（Depth First Search）
深度搜索（Depth-First Search，DFS）中的"深度"指的是在搜索問題的解空間時，演算法首先沿著一條路徑深入到解空間中，直到達到最深處或者無法再深入為止；然後再回退並繼續探索下一個分支。
雖然 在上一篇 二叉樹 中沒提及這個名稱，但其實上篇涉及的幾個演算法問題解法都是深度搜索；DFS通常使用遞歸或棧（堆棧）數據結構來實現，在這裡不妨再練習一題。
LeetCode 113. 路徑總和 II 【中等】
給你二叉樹的根節點 root 和一個整數目標和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等於給定目標和的路徑。葉子節點 是指沒有子節點的節點。
廣度優先搜索（Breadth First Search）
廣度搜索（Breadth-First Search，BFS）中的"廣度"指的是演算法在搜索問題的解空間時，從起始點開始逐層地向外擴展，以確保先探索當前層的所有節點，然後再深入到下一層的節點，層層展開。
所謂“層層展開” 例如在二叉樹結構中，根節點是第0層，子節點是第1層，孫子節點是第2層，依此類推。BFS通常使用隊列數據結構來實現。
LeetCode 515. 在每個樹行中找最大值【中等】
給定一棵二叉樹的根節點 root ，請找出該二叉樹中每一層的最大值。
LeetCode 695. 島嶼的最大面積【中等】
給你一個大小為 m x n 的二進位矩陣 grid 。
島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這裡的「相鄰」要求兩個 1 必須在 水平或者豎直的四個方向上 相鄰。你可以假設 grid 的四個邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數目。計算並返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。
總結下
- 隊列（Queue）、棧（Stack）數據結構開始，引出到 雙端隊列（Double-Ended Queue）；
- 深度搜索（Depth-First Search）的基本應用，通常使用遞歸或棧（堆棧）數據結構來實現；
- 廣度優先搜索（Breadth First Search）的基本應用，通常使用隊列數據結構來實現。
