Hoi hoi！
我是 @nyaomaru，一位連遊戲音效都做不好而苦惱的前端工程師。😿
你已經用過 DSA View View 了嗎？👀👀
https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo
DSA View View 讓你能透過視覺化實作實際執行的過程，來理解 DSA。
在前一篇文章中，我們看了：
- Two Sum
- Binary Search
- Bubble Sort
這次，讓我們再試三個經典題目：
- 有效的括號
- 反轉鏈結串列
- 二元樹的最大深度
這三題分別引入三個非常不同的觀念：
Stack
Pointer manipulation
Recursion而且只要我們盯著最終程式碼看，這三者都很容易變得令人困惑。
所以，讓我們看看實際發生了什麼。👀
我自己也還在學 DSA，所以一起學吧！😸
🥞 有效的括號
先從 有效的括號 開始。
假設我們有這個字串：
()[]{}每個左括號都有對應的右括號。
所以這是有效的。✅
但是這個
([)]就無效。❌
為什麼？
因為括號關閉的順序錯了。
(
[
)
][ 應該要先於 ( 被關閉。
那我們要怎麼追蹤這個順序呢？
使用堆疊
堆疊（stack） 遵循一個很簡單的規則：
最後放進去的東西，會最先被拿出來。
這叫做 LIFO（Last In / First Out，後進先出）。
想像一下疊盤子。
🍽️ ← 先拿走
🍽️
🍽️最後放上去的盤子，會是第一個能拿走的。
括號也一樣。
如果我們看到：
(
[
{那括號就必須以相反順序關閉：
}
]
)所以堆疊非常適合這個問題。
以下是實作：
function isValid(s: string): boolean {
const stack: string[] = [];
const pairs: Record<string, string> = {
")": "(",
"]": "[",
"}": "{",
};
for (const char of s) {
if (char === "(" || char === "[" || char === "{") {
stack.push(char);
continue;
}
if (stack.length === 0) return false;
const target = stack.pop();
if (target !== pairs[char]) {
return false;
}
}
return stack.length === 0;
}重點在於 stack 的變化。
我們用
([])來看。
一開始
stack = []我們看到
(這是左括號。
推入堆疊。
stack = ["("]接著，
[再推一次。
stack = ["(", "["]然後，
]這是右括號。
它應該要關閉什麼？
[而目前堆疊頂端是什麼？
[完全正確。✅
所以把它彈出。
stack = ["("]最後，
)它應該要關閉
(堆疊頂端也正好是
(彈出！
stack = []我們結束時堆疊是空的。
有效！🎉
無效範例呢？
考慮
([)]我們一樣從頭開始。
(
↓
stack = ["("]
[
↓
stack = ["(", "["]接著遇到
)) 需要的是
(但我們堆疊頂端是
[它們不匹配。
expected: (
actual: [所以我們立刻知道字串無效。
複雜度
我們只會走訪字串一次。
Time: O(n)
Space: O(n)在最糟的情況下，堆疊可能會包含所有左括號。
👀 讓我們把它視覺化
這正是堆疊變得更容易理解的地方。
當我們只看：
stack.push(char);以及
stack.pop();時，很容易搞不清楚堆疊裡面到底有哪些東西。
特別是像這種：
({[]})現在頂端是什麼？
我們到底要關閉哪個左括號？
與其把所有東西都記在腦中，不如一步一步看堆疊如何變化。
<!-- Add Valid Parentheses DSA View View share embed here -->
概念上，我們可以看到：
(
↓
[(]
{
↓
[(, {]
[
↓
[(, {, []
]
↓
[(, {]
}
↓
[(]
)
↓
[]就是這個意思。
記住左括號，並且永遠先匹配最近的一個。
堆疊突然就沒那麼神祕了。🥞😸
🔗 反轉鏈結串列
接下來，讓我們反轉一個鏈結串列。
假設我們有：
1 → 2 → 3 → 4 → 5我們想要：
5 → 4 → 3 → 2 → 1乍看之下，這很簡單。
反過來就好！
但鏈結串列和陣列有點不同。
在陣列中，值是存在像這樣的位置裡：
0 1 2 3 4
↓ ↓ ↓ ↓ ↓
1 2 3 4 5但鏈結串列是由節點組成，每個節點都指向下一個節點。
1 → 2 → 3 → 4 → 5 → null每一條箭頭都很重要。要反轉串列，就得反轉這些箭頭。
1 ← 2 ← 3 ← 4 ← 5而問題也正是在這裡開始變得容易混亂。
因為如果我們太早改掉一條箭頭……
可能就會失去串列剩下的部分。😿
三個重要變數
常見的迭代解法會使用三個變數：
prev
current
next以下是實作：
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let current = head;
while (current !== null) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}它很短。
但這幾行裡其實發生了很多事。
讓我們仔細追蹤。
一開始我們有：
1 → 2 → 3 → null而且：
prev = null
current = 1步驟 1：儲存下一個節點
首先：
const next = current.next;所以：
next = 2為什麼需要這樣做？
因為我們接下來要改變：
1 → 2如果我們在沒記住 2 的情況下就改掉這條箭頭，我們就會失去存取串列剩餘部分的能力。
所以第一步是：
先把下一步要去哪裡記住。
步驟 2：反轉箭頭
現在：
current.next = prev;原本是：
1 → 2但 prev 是：
null所以現在變成：
1 → null第一條箭頭已經反轉了。
步驟 3：移動 prev
接著：
prev = current;所以：
prev = 1步驟 4：移動 current
最後：
current = next;我們剛剛已經先把 2 存起來了。
所以現在：
current = 2此時狀態如下：
null ← 1 2 → 3 → null
↑ ↑
prev current然後我們再做一次完全相同的事情。
先儲存：
next = 3反轉：
2 → 1移動：
prev = 2
current = 3現在：
null ← 1 ← 2 3 → null
↑ ↑
prev current再來一次：
next = null反轉：
3 → 2移動：
prev = 3
current = null現在變成：
null ← 1 ← 2 ← 3
↑
prev迴圈會停止，因為：
current === null而 prev 就是新的頭節點。
所以：
return prev;完成！🎉
複雜度
每個節點只會被走訪一次。
Time: O(n)
Space: O(1)我們沒有建立另一個鏈結串列。
我們只是移動幾個指標而已。
👀 讓我們把它視覺化
這正是我覺得光看程式碼很難理解的那種題目。
這四行：
const next = current.next;
current.next = prev;
prev = current;
current = next;看起來很簡單。
但我第一次看到這種程式時，腦中總會冒出問題：
等等。
- current 現在在哪？
- 我們有沒有把 next 弄丟？
- 哪一條箭頭被改了？
- prev 到底指向哪裡？😿
當我們把每一步視覺化後，就能真的跟著指標移動。
prev current
↓ ↓
null 1 → 2 → 3
↓↓↓
null ← 1 2 → 3
↑ ↑
prev current
↓↓↓
null ← 1 ← 2 3
↑ ↑
prev current
↓↓↓
null ← 1 ← 2 ← 3
↑
prev當我們不再把它想成四個神祕的指定敘述時，這個演算法就變得簡單多了。
它其實只是：
儲存 next
↓
反轉箭頭
↓
移動 prev
↓
移動 current
↓
重複很不錯吧！🔗😸
🌳 二元樹的最大深度
最後，讓我們看看一棵樹。
考慮這棵二元樹：
3
/ \
9 20
/ \
15 7它的最大深度是多少？
從根節點到葉節點的最長路徑包含三個節點：
3
↓
20
↓
15所以答案是：
3那我們要怎麼算出來？
先想一棵更小的樹
假設我們站在某個節點上。
其實不需要一次理解整棵樹。
我們只需要問：
左子樹有多深？
右子樹有多深？然後選較大的那一邊。
再加上目前這個節點的 1。
這正是這段實作在做的事情。
function maxDepth(root: TreeNode | null): number {
if (root === null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}關鍵概念是：
Math.max(leftDepth, rightDepth) + 1;但遞迴常常讓人覺得很奇怪。
當我們呼叫：
maxDepth(root.left);目前這個函式去哪了？
那些呼叫最後又是怎麼變成一個數字的？
讓我們用一個小例子來看。
1
/ \
2 3
/
4我們從：
1開始。
但在 1 知道自己的深度之前，它先問左子節點：
maxDepth(2)節點 2 再問：
maxDepth(4)節點 4 沒有子節點。
所以兩邊最後都會到達：
null而：
maxDepth(null);回傳：
0因此節點 4 可以算出：
max(0, 0) + 1
= 1現在回到節點 2。
它的左邊深度是：
1右邊是 null：
0所以：
max(1, 0) + 1
= 2再回到節點 1。
最後它的右子樹也會回傳：
1所以節點 1 得到：
leftDepth = 2
rightDepth = 1並計算：
max(2, 1) + 1
= 3答案：
3🎉
有趣的地方：往下走，再往上回來
這就是遞迴有趣的地方。
首先，函式呼叫會先往樹的下方走。
1
↓
2
↓
4
↓
null但答案是在往上回傳時建立起來的。
null → 0
4 → 1
2 → 2
1 → 3所以遞迴不只是：
一直呼叫同一個函式。
其實有兩個方向。
往下走
↓
到達基底情況
↓
把回傳值往上傳這裡的基底情況是：
if (root === null) {
return 0;
}如果沒有它，遞迴就沒有停止的地方。
複雜度
每個節點只會被走訪一次。
Time: O(n)遞迴呼叫堆疊取決於樹的高度。
Space: O(h)其中 h 是樹的高度。
如果是平衡樹，大約是：
O(log n)最糟的情況下，如果樹長得像鏈結串列：
1
\
2
\
3
\
4深度可能變成：
O(n)👀 讓我們把它視覺化
遞迴大概是我最喜歡拿來視覺化的例子。
因為最後的實作非常短：
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;但這些函式呼叫裡面藏了很多東西。
在閱讀程式碼時，感覺就像：
maxDepth()
在 maxDepth() 裡
在 maxDepth() 裡
在 maxDepth() 裡
...我們現在到底在哪？😿
當我們逐步執行時，就能同時看到兩個部分：
往下走
1
↓
2
↓
4
↓
null以及：
回來時
null → 0
↓
4 → 1
↓
2 → 2
↓
1 → 3這會讓遞迴的概念清楚很多。
向更小的子問題要答案，再用那些答案來建立目前的答案。
🌳😸
🧠 我們到底學到了什麼？
這三題看起來完全不同。
但它們各自介紹了一種非常實用的思考方式。
有效的括號
當最晚加入的專案需要最先處理時，就使用堆疊。
我最後打開的是哪個？反轉鏈結串列
當你要改變參照時，先把之後還需要的東西存起來，再切斷舊連結。
在改這個指標之前，我下一步要去哪？二元樹的最大深度
把問題拆成同樣問題的更小版本。
我能不能從我的子節點那裡拿到答案，再用它們建立自己的答案？這也是我喜歡把這些題目一起學的原因之一。
它們的實作都不長。
但每一題都引入了完全不同的心智模型：
Stack
Pointer
Recursion而這些心智模型，比語法本身難學得多。
有時候程式碼只告訴我們發生了什麼。
但我也想知道它是怎麼發生的。
我想把它看見。👀👀
🎯 結論
這篇文章中，我們看了：
- 使用堆疊處理有效的括號
- 使用指標操作反轉鏈結串列
- 使用遞迴計算二元樹的最大深度
更重要的是，我們在每個演算法執行時都跟著狀態一起看。
我們看著堆疊改變。
stack.push() / stack.pop()我們看著指標在鏈結串列中移動。
prev
current
next我們也看著遞迴呼叫往樹下走，再把答案回傳上來。
這正是我打造 DSA View View 的目的。
https://dsa-view-view.vercel.app
你可以撰寫或載入 TypeScript 實作，用自己的輸入執行，並在執行過程中前進或後退查看。
如果你也在學 DSA，試著把其中一題一步一步看過去。
尤其是當某個解法讓你覺得：
我每一行都看得懂……但整體就是還是不懂。😿
看見執行過程，或許能把那些片段串起來。
如果你有希望我下一篇介紹的 DSA 題目，也請在留言告訴我！
我自己也還有很多演算法要學。😸
讓我們一起鍛鍊 DSA 肌肉吧！💪
如果你喜歡 DSA View View，請幫它按個星星 ⭐
https://github.com/nyaomaru/dsa-view-view
我們下一篇文章見！
1) --- 會變成分隔線（上一行必須是空白）
2) # 會變成一級標題
3) ## 會變成二級標題
4) ### 會變成三級標題
5) **粗體文字**會顯示粗體文字
6) ```當第一行與最後一行會顯示程式碼
7) 請搜尋 Markdown 語法，了解各種格式
