CodeFarmer 技術週報 #2 - Binary Tree
本期來複習 Tree 這個資料結構並試著解 Binary Tree 相關的題目
嗨嗨大家，歡迎閱讀第 2 期的 CodeFarmer 技術週報！
在最開始前，要先特別感謝
在上一期的雙週報中推薦分享，以及感謝電子報前輩 《古古的後端筆記》 在 Threads 上的轉貼分享，讓訂閱人數有了不少成長。也感謝各位讀者願意訂閱支持，雖然原本初衷是週期性地輸出自己比較粗糙的學習筆記，但仍然期待未來文章品質能逐漸提升到自己滿意的樣子，若內容有什麼錯誤、問題、更好的解釋方法也都歡迎透過以下管道與我討論：
Email：codefarmer.tw@gmail.com
正值年初，新年新目標之一是來把之前刷到一半的 Grind 75 衝完，這週就先從 Binary Tree 這個資料結構的題目開始吧。
關於 Tree 這個資料結構
解題前簡單複習一下 tree 這個資料結構，深入複習後發現要講起來水很深，有各式各樣的變形，一直往下挖會看到像是 B+ tree 是 MySQL 背後的儲存引擎這類資訊，但這裡先簡單整理基本相似的名詞關係：
Graph：資料結構中的 Graph 指的是一個由節點 (node、vertex) 與邊 (edge) 組成的結構
Tree
可視為一種非封閉且連通的 graph
基本的樹結構中會有根節點 (root node)，與底下許多的子節點
若某個節點底下沒有其他子節點則稱為 leaf node
Binary Tree (二元樹)
若樹中的每個節點最多只能有 2 個子節點，則稱為二元樹
其他分類
Full Binary Tree：每個節點底下的節點數只有 0 與 2
Complete Binary Tree：除最後一層外每層節點數全滿，且最後一層節點都靠左
Perfect Binary Tree：符合 Full Binary Tree 與 Complete Binary Tree，也就是每一層節點數全滿
Binary Search Tree (BST)
特製化的 binary tree，節點中的值需要符合以下規則：
左子樹的值皆小於 root 的值
右子樹的值皆大於 root 的值
每個子樹也都符合以上規範
一般實作上不允許重複的值
用途：方便更快的搜尋、新增、刪除資料
特化：另外為了解決樹高平衡問題，有 AVL tree、B-Tree 等特化結構
解題：二元樹的最大深度
複習完資料結構的基本知識後，就用 Grind 75 在 Binary Tree 主題中相對單純的「104. Maximum Depth of Binary Tree」這題，並搭配白板題面試框架來試試水溫吧。
題目描述
給定一個二元樹的根節點 root，返回其最大深度。二元樹的最大深度是從根節點到最遠 leaf node 的最長路徑上的節點數量。
範例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：3範例 2：
輸入：root = [1,null,2]
輸出：2限制條件
樹中節點的數量範圍為
[0, 10^4]-100 <= Node.val <= 100
問題釐清
輸入為 TreeNode 或 null，輸出為 number？應不需要處理不合法輸入？
最大深度從範例一看起來會包含 root 這層？
若輸入為空樹則回傳 0 即可？
樹的節點數可能達到一萬個，是否需考慮極度傾斜樹的狀況？
提出測試案例
能通過範例一、二
傳入空樹時回傳 0
一萬個節點的左傾樹確認不會 stack overflow
提出思路
因為跟深度有關，直覺用 DFS (深度優先搜尋演算法) 來解比較單純，而 DFS 的實作可以有兩種方式：
遞迴
好處：程式碼簡潔
壞處：在樹高度過深時有可能有 stack overflow 問題
stack 搭迴圈
好處：能避免 stack overflow 問題
壞處：程式碼稍微複雜些
如果先以遞迴來解題的話以註解表示：
實作
結果發現遞迴版本的實作意外單純：
撰寫測試
先來把上面的測試案例實作成單元測試確認是否通過，程式好讀版可以參考此連結，這邊只列出比較關鍵的壓測部份：
試著在這個測試中去調整節點數 (nodeCount) 的參數做一下壓測，發現在開啟了 Vitest 中關於改善效能的 pool: threads 設定後，10^4 個節點是可以正常通過，但提升到 10^5 就會遇到 RangeError: Maximum call stack size exceeded 這個關於 stack overflow 的錯誤，也就是說在遞迴深度過深時會遇到的問題，而解法就像前面提到的可以改用迴圈搭配 stack 的資料結構來嘗試解決。
關於 Vitest 的 pool 這個設定，主要是用來決定測試的多工執行方式。
預設的設定會將測試跑在不同的 child process 上，但這在遇到測試比較複雜時可能會佔用過多的記憶體空間。
因此當今天有遇到效能問題時，參考文件建議有一招是可以改成使用 worker_threads，也就是只跑在不同的執行緒上來提升效能。
又好奇去看這是不是只有 Vitest 特製的設定，找到 Jest 中也有一個 workerThreads 的設定，關於這兩者的差別還沒太深入研究，先筆記在這。
其他解法：stack 搭迴圈版
試試 stack 搭迴圈版，註解版本：
再來依照上述的註解來實作程式：
此時如果再次用 10^5 個節點的測試實測能正確通過，一直加節點到 10^7 才會開始出現卡頓感。也應證了迴圈的解法雖然寫法上較複雜，但在面對更極端的資料量時有更大的容忍度，這也是為什麼最一開始在釐清問題時要去確認「是否需考慮極度傾斜樹的狀況？」。
關於 Binary Tree 的其他解題
在刷題時試了跨主題刷、同主題深入刷兩種方式，覺得還是後者比較適合自己，因此這幾天也陸續做了許多相關的題目，有興趣的讀者也可以參考以下連結：
尤其是 297 這題 hard，覺得其實程式實作上並不困難，但難在他屬於比較開放式的題型，因為沒有提供太多限制的狀況下，如果以面試框架來回答的話其實在前面釐清問題與測試案例上就會要考慮到蠻多點的，推薦一讀。
本期推薦內容
雖然本週報比較不是追最新消息的定位，但如果當期有看到一些不錯的內容也試著統整在最後面，也算是解決以前在 IG 限動、Threads 上分享時資訊零散的問題：
ByteByteGo 在社群上分享他們開了另一個比較偏向做演算法教學內容的 Youtube 頻道 — Coding Patterns，有興趣可以訂閱
近期看到一個類似 Great Frontend 版型的買斷型內容平台 — SWE Quiz，看起來像是提供一些全端系統設計面試的整理。裡面也有提供優質的免費電子報，看他第一篇非常完整的寫到在系統設計面試中「如何選擇適合的資料庫」，直接先訂起來再說
最近在社群上、朋友推坑、電子報一直看到有個酷酷的新玩具 — Ghostty，原本幾個月前才剛換到 Warp，昨天也分享了一些關於這工具的隨手筆記
以上就是本期的 CodeFarmer 技術週報的所有內容了，若內容有什麼錯誤、問題、更好的解釋方法也都歡迎透過以下管道與我討論：
Email：codefarmer.tw@gmail.com
喜歡本期的內容也歡迎免費訂閱週報，那我們就下週三見了：