來征服資料結構與演算法吧 | 連 Google 面試都在考的 Binary Tree
Hi！大家好，我是神 Q 超人！在這篇文章裡，會先介紹 binary tree 的資料結構，與如何使用 JavaScript 實作，最後一樣會挑幾題演算法來練練手，學習一下和 Tree 結構形影不離的深度搜尋法（DFS，Depth-first Search）與廣度搜尋法（BFS，Breadth-first Search），希望可以讓大家熟悉 binary tree 的資料結構與用法。
題外話是，原本在寫完 linked list 那篇文章 時就要寫 binary tree 的，但莫名其妙被其他有趣的主題插隊了。 😂
Binary Tree
介紹
提到 binary tree 之前先來說說 tree 結構，如果之前有學過 linked list 的話就會知道（還沒看過可以點 這裡），在 linked list 裡都是一個 node（節點）對應另一個 node，但是 tree 結構下的 node 可以擁有很多 node，比較常遇到的 tree 結構應該就是資料夾，一個資料夾中有很多檔案或資料夾，而某個資料夾裡又有它自己的檔案，這就是一對多的 tree 結構。把 tree 結構畫成圖會長這樣子：
那 binary tree 呢？與 tree 不同的是，binary tree 結構裡的每一個 node 最多只會有 2 個 node，分別放在左邊和右邊。把 binary Tree 畫成圖會長這樣：
不論是 tree 或是 binary tree，只要是上方沒有任何 node 的第一個 node 就被稱作為 root，另一方面如果某個 node 下沒有任何子 node 的話，我們就會稱那個 node 為 leaf node，就是葉子的意思。
Binary tree 在應用上和 tree 比較不一樣的部分是，binary tree 會用來做排序或是搜尋（排序的部分，也可以看這裡呦！搜尋的部分可以找 binary search tree）。
下方是一個 binary tree 的程式碼實作：
在程式碼實作中，nodeA 下的 nodeB 和 nodeC 分別放在 left 與 right 屬性，然後每個 node 的值就放在 val 屬性裡，如此一來就能夠達到每個 node 對應到最多 2 個 node 了。
稍微了解 binary tree 後，就能開始從 LeetCode 上找一些相關題目來練習一些操作！
深度搜尋法（DFS，Depth-first Search）
首先第一題是 Symmetric Tree，這道題目會給你一個 binary tree，並且要你判斷這個 binary tree 是不是對稱的，舉例下面這個例子來說：
Input: root = [1, 2, 2, null, 4, 4, null]
Output: true雖然 input 的 root 表現得很像 array 一樣，但其實是代表著從上到下，由左到右排列成 binary tree，如果遇到 null 的狀態就代表該位置是沒有 node 的，以圖呈現會是：
如果排列出來的結果是像上方的 binary tree，從中間切一半，左右兩邊都是對稱的，就回傳 true。下方另外一組範例，大家也可以試著畫出來，就能知道為什麼是 false 囉：
Input: root = [1, 2, 2, null, 3, null, 3]
Output: false那該如何從最上層開始一直往下判斷到每個節點呢？這時候就需要用到深度搜尋法（DFS，Depth-first Search）了！DFS 是一種遞迴，這個遞迴會從 root 開始，一直往下方的 node 找到符合條件，或是到 leaf node 無法再往下找為止。
通常在做這種題目的時候，我都會先將結束判斷的條件寫在另一個 function 中。例如在這道題目中，這個方法接收了兩個 node 後，會有三個狀況：
- 如果其中一個 node 是 null 的話，就回傳 false
- 如果兩個 node 的值不相同，就回傳 false
- 如果兩個 node 都是 null，代表目前已經找到最後了，沒有更深的 node 需要繼續判斷，就回傳 true
把這三個條件寫在 DFS 的方法中會變成：
在這三個判斷中，等於已經處理了「leaf node」、「node 的值不同」的情況，那如果「不是 leaf node，而且當前的 node 的值又相同」的話呢？那就要再把接下來要比較的兩個 node 放進 dfs 這個方法執行！一直到觸發終止條件。至於該放哪兩個 node 進來比較呢？讓我們來分析一下這個案例：
Input: root = [1, 2, 2, null, 4, 4, null]
Output: true下面解釋會有點複雜，會再加上圖片輔助。
以1（root）來說，要判斷的兩個 node 分別是 2（left）和 2（right）：
所以我們就可以先把這兩個 root 的 left 和 right 先放進 dfs 裡面，也要考慮到 root 一開始就是 null 的情況：
接下來到 2（left）這個 node 時，要判斷的兩個 node 就不是 2（left）的 null（left） 和 4（right），因為不論這兩個值是否相等，都和整顆 binary tree 有沒有對稱無關：
要比較的應該是 2（left）的 null（left）和 2（right）的 null（right），以及 2（left）的 4（right）和 2（right）的 4（left）：
把上述的圖轉化為程式碼加入 dfs 裡，讓 dfs 可以持續比較，並回傳最後的結果：
其實深度搜尋法（DFS，Depth-first Search）就是利用遞迴不斷的往下一層 node 做邏輯判斷，在使用上需要注意的就是，一定要先考慮到 DFS 最後的結束與回傳條件，否則遞迴就會變成無窮的，永遠跑不出結果。DFS 其實需要一些想像力，去思考 node 如何跑到下一層去，如果是一開始的練習階段，建議可以用 console.log 把每一次 DFS 裡處理的 node 都印出來看看，會對整個執行流程清楚很多。
100. Same Tree 也是很適合練習 DFS 的一題，只是從一個 binary tree 變成兩個。
廣度搜尋法（BFS，Breadth-first Search）
第二題是 102. Binary Tree Level Order Traversal，這題只用文字會有點抽象，讓我們看看範例再搭配圖解說：
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [9, 20], [15, 7]]上方 input 的 binary tree 轉化為圖會長這樣子：
得到 binary tree 後，我們就要像是綠色框框一樣，將每一層的值由左至右放入 array 中，像是第一層的 array 就是 [3]、第二層是 [9, 20]、第三層是 [15, 7]，接著再將各層的 array 依照層數放入另一個 array 中，變成一個二維的 array：[[3], [9, 20], [15, 7]]。
在瞭解題意是要我們搜集每層的 node 之後，就可以知道像剛剛那種每次都會直接往下找 node 的 DFS 是行不通的，所以就輪到廣度搜尋法（BFS，Breadth-first Search）出馬了。
BFS 與 DFS 會使用當前 node 的 left 與 right 繼續往下執行不同，BFS 會一層一層由左至右的讀取，在讀完當前的一層後才會進入下一層。另外，在使用 BFS 的時候，通常都會搭配 Queue 的資料結構來紀錄每一層要讀取的 node 數，沒問題的話，就開始解題囉！
在這篇文章裡面，為了簡化 Queue 的邏輯，就直接使用 array 的 push 和 shift 當作 enqueue 和 dequeue 的實作，但時間複雜度還是會和真正的 Queue 不一樣，因此執行時間會有些許的不同，詳情可以看看 這篇文章。
再來就是 BFS 的核心邏輯了，BFS 的讀取方法是一層一層由左至右讀取 node，而 binary tree 的第一層一定會是一個 root（除非 binary tree 是 null），因此我們先確定 binary tree 不是 null 後，就先把 root 塞進 queue 裡面：
現在的 queue 裡面有個 root，而 root 是第一層唯一一個 node，也就是說如果我用 for 迴圈把現在 queue 裡面擁有的 node 數量跑過一遍，就等於跑完第一層了：
如果執行完上方的程式碼，那 level 裡面會有 root 的 node 值，但是就沒下一層了，怎麼辦？很簡單，只要在跑這一層的時候，把下一層存在的 node 也裝進 queue 裡面就好啦！因為下一層存在的 node，就等於這一層 node 的 left 和 right：
我們已經做到先塞好下一層的 node 了，但要怎麼到下一層呢？其實很簡單，這可以直接用 while 去判斷，如果 queue 還不是空的，就代表 queue 裡還有下一層的 node，如果是空的就代表全都跑完啦：
在上方的步驟中，也順便加入了 result，每次用 for 把當層的所有 node 值都放進 level 後，就把 level 放進 result 裡，最後只要回傳 result 就搞定啦！
BFS 相對於 DFS 來說更容易理解，畢竟遞迴本身就不是那麼直觀的東西，而且 BFS 幾乎就是一個公式，只要需要根據題目稍微修改在 for 裡面拿到 node 後要做的事情就好。
其他可以用 BFS 解的題目是 103. Binary Tree Zigzag Level Order Traversal，這題解法和剛剛的 102. Binary Tree Level Order Traversal 很類似，只要再多一個判斷的邏輯就好。
226. Invert Binary Tree
最後來聊聊有關 Google 面試的知名故事，那就是 Homebrew 的作者到 Google 面試時被說了：「我們 90% 的工程師都在用你開發的 Homebrew，但因為你無法在白板上翻轉 binary tree，所以我們無法雇用你（原始貼文）」
在這篇文章中先不評論面試環境如何，但是連 Google 都拿來當考題的 Invert Binary Tree 就很值得朝聖一下，那就來看看 LeetCode 上的案例吧：
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]這一題要求的是將傳進來的 binary tree 的所有 node 左右對調，大家可以試著將上方的 input 與 output 都畫成 tree 的圖，就能更清楚知道題目的需求。
既然是從 root 開始，將每個 node 的 left 和 right 都對調，這種用當前的 node 不斷往下執行對調的方式，是不是秒想到 DFS？沒錯！這題就是要用 DFS！
題目要求我們對每層 node 做翻轉，因此在 dfs 的方法裡寫下把 node 的 left 和 right 對調的邏輯，只是在翻轉的時候要注意一下當前的 node 是不是 null，是的話就直接 return，不執行任何東西：
完成 dfs 內的邏輯後，直接從外面把 root 傳給 dfs，執行完也等於把 binary tree 都翻轉完了：
這次的 binary tree 比起 linked list 來說，要說明某些步驟和解題邏輯的挑戰真的大超多，而且對能寫字就不畫圖的我，也在這一系列完全感受到了文字有多無力 😂，如果大家在看文章真的有搞不懂的地方，請一定要留言告訴我，我會再繼續琢磨如何更明確解釋的！
那最後如果文章內容有任何問題，再麻煩各位留言告訴我，我都會盡快修改，非常感謝！🙌
