Học Valid Parentheses, Reverse Linked List và Tree Max Depth bằng trực quan từng bước với DSA View View 👀👀
Học Valid Parentheses, Reverse Linked List và Tree Max Depth bằng trực quan từng bước với DSA View View 👀👀
Hoi hoi!
Mình là @nyaomaru, một frontend engineer đang vật lộn với việc làm sound effect cho game. 😿
Bạn đã thử DSA View View chưa? 👀👀
https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo
DSA View View là một tool giúp bạn hiểu DSA bằng cách trực quan hóa cách implementation thực sự chạy ở runtime.
Trong bài trước, chúng ta đã xem ba bài toán:
- Two Sum
- Binary Search
- Bubble Sort
Lần này, chúng ta sẽ tiếp tục với ba bài classic khác:
- Valid Parentheses
- Reverse Linked List
- Maximum Depth of Binary Tree
Ba bài này sử dụng ba mental model hoàn toàn khác nhau:
Stack
Pointer manipulation
Recursion
Và cả ba đều có một điểm chung:
Nếu chỉ nhìn final code, rất dễ có cảm giác:
Khoan đã... bây giờ chuyện gì đang xảy ra vậy??? 🙀
Vậy nên lần này, hãy cùng xem những gì thực sự xảy ra trong runtime. 👀
Mình cũng vẫn đang học DSA, nên cùng học với nhau nhé! 😸
🥞 Valid Parentheses
Bắt đầu với Valid Parentheses.
Giả sử chúng ta có string này:
()[]{}
Mỗi opening bracket đều có một closing bracket tương ứng.
Vì vậy, string này valid. ✅
Nhưng string này:
([)]
lại invalid. ❌
Tại sao?
Vì các bracket được đóng sai thứ tự.
(
[
)
]
Chúng ta phải đóng [ trước khi đóng (.
Vậy làm sao để nhớ thứ tự này? 🤔
Dùng Stack
stack có một rule rất đơn giản:
Thứ được thêm vào cuối cùng sẽ được lấy ra đầu tiên.
Đây là LIFO — Last In / First Out.
Hãy tưởng tượng một chồng đĩa:
🍽️ ← lấy ra trước
🍽️
🍽️
Chiếc đĩa được đặt lên trên cùng sau cùng sẽ là chiếc được lấy ra trước.
Parentheses cũng giống như vậy.
Nếu opening brackets xuất hiện theo thứ tự:
(
[
{
thì khi đóng, chúng phải xuất hiện theo thứ tự ngược lại:
}
]
)
Vì vậy stack rất hợp với bài toán này.
implementation trông như sau:
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;
}
Điều quan trọng không chỉ là push hay pop.
Mà là:
Nội dung của
stackthay đổi như thế nào?
Hãy thử với:
([])
Ban đầu:
stack = []
Đầu tiên xuất hiện:
(
Đây là opening bracket.
Push.
stack = ["("]
Tiếp theo:
[
Push lần nữa.
stack = ["(", "["]
Sau đó xuất hiện:
]
Đây là closing bracket.
Nó cần đóng cái gì?
[
Vậy ở top của stack hiện tại là gì?
[
Perfect! ✅
Vậy chúng ta loại nó ra.
stack = ["("]
Cuối cùng:
)
Nó cần đóng:
(
Và top của stack cũng là:
(
Pop!
stack = []
Đi đến cuối string, stack đã rỗng.
Valid! 🎉
Trường hợp Invalid thì sao?
Hãy xem:
([)]
Phần đầu vẫn giống nhau.
(
↓
stack = ["("]
[
↓
stack = ["(", "["]
Sau đó xuất hiện:
)
) cần match với:
(
Nhưng top của stack lại là:
[
Không khớp.
expected: (
actual: [
Vì vậy chúng ta biết ngay string này invalid.
Complexity
Chúng ta chỉ đi qua string một lần.
Time: O(n)
Space: O(n)
Trong worst case, tất cả character đều là opening brackets và đều được đưa vào stack.
👀 Hãy View View nó
Đây là một chỗ mà visualization giúp rất nhiều.
Nếu chỉ nhìn:
stack.push(char);
hoặc:
stack.pop();
rất dễ quên:
Khoan, bây giờ trong stack đang có gì?
Đặc biệt với một string như:
({[]})
Bracket nào đang ở top?
Chúng ta đang cố đóng opening bracket nào?
Thay vì giữ tất cả trong đầu, hãy xem stack thay đổi step-by-step.
Về mặt ý tưởng, nó sẽ giống như thế này:
(
↓
[(]
{
↓
[(, {]
[
↓
[(, {, []
]
↓
[(, {]
}
↓
[(]
)
↓
[]
Chỉ vậy thôi.
Ghi nhớ các opening brackets, rồi luôn match từ bracket được thêm gần nhất.
Khi nhìn theo cách này, stack tự nhiên bớt bí ẩn hẳn. 🥞😸
🔗 Reverse Linked List
Tiếp theo, hãy reverse một linked list.
Giả sử chúng ta có:
1 → 2 → 3 → 4 → 5
Và muốn biến nó thành:
5 → 4 → 3 → 2 → 1
Nhìn qua thì có vẻ đơn giản.
Chỉ cần đảo ngược thôi mà!
Nhưng linked list hơi khác array.
Trong array, các value nằm ở những position như thế này:
0 1 2 3 4
↓ ↓ ↓ ↓ ↓
1 2 3 4 5
Còn trong linked list, mỗi node trỏ tới node tiếp theo.
1 → 2 → 3 → 4 → 5 → null
Những mũi tên này mới là phần quan trọng.
Muốn reverse linked list, chúng ta phải đảo hướng những mũi tên đó.
1 ← 2 ← 3 ← 4 ← 5
Và từ đây mọi thứ bắt đầu hơi rối.
Bởi vì nếu đổi một pointer quá sớm...
chúng ta có thể làm mất phần còn lại của list. 😿
Ba Variable Quan Trọng
Một iterative solution phổ biến sử dụng ba variables:
prev
current
next
implementation như sau:
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;
}
Rất ngắn.
Nhưng khá nhiều thứ xảy ra chỉ trong vài dòng này.
Hãy đi từng bước.
Bắt đầu với:
1 → 2 → 3 → null
State hiện tại:
prev = null
current = 1
Step 1: Lưu Node tiếp theo
Đầu tiên:
const next = current.next;
Vậy:
next = 2
Tại sao cần lưu nó trước?
Bởi vì ngay sau đó chúng ta sẽ thay đổi:
1 → 2
Nếu đổi mũi tên mà chưa lưu 2, chúng ta có thể mất đường đi tới phần còn lại của list.
Vì vậy, bước đầu tiên thực chất là:
Trước khi phá connection cũ, hãy nhớ nơi cần đi tiếp theo.
Step 2: Reverse mũi tên
Tiếp theo:
current.next = prev;
Ban đầu:
1 → 2
Nhưng hiện tại:
prev = null
nên nó trở thành:
1 → null
Mũi tên đầu tiên đã được reverse.
Step 3: Di chuyển prev
Tiếp theo:
prev = current;
Vậy:
prev = 1
Step 4: Di chuyển current
Cuối cùng:
current = next;
Chúng ta đã lưu 2 trước đó.
Nên:
current = 2
State bây giờ:
null ← 1 2 → 3 → null
↑ ↑
prev current
Sau đó làm chính xác điều tương tự lần nữa.
Lưu:
next = 3
Reverse:
2 → 1
Di chuyển:
prev = 2
current = 3
State:
null ← 1 ← 2 3 → null
↑ ↑
prev current
Thêm một lần nữa.
next = null
Reverse:
3 → 2
Di chuyển:
prev = 3
current = null
Cuối cùng:
null ← 1 ← 2 ← 3
↑
prev
Loop kết thúc vì:
current === null
Và prev đã trở thành head mới.
Vì vậy:
return prev;
Done! 🎉
Complexity
Mỗi node chỉ được visit một lần.
Time: O(n)
Space: O(1)
Chúng ta không tạo một linked list mới.
Chỉ di chuyển vài pointers.
👀 Hãy View View nó
Đây chính xác là loại code mà mình thấy rất khó hiểu nếu chỉ đọc.
Chỉ bốn dòng này:
const next = current.next;
current.next = prev;
prev = current;
current = next;
Mỗi dòng riêng lẻ đều rất đơn giản.
Nhưng lần đầu nhìn cả bốn cùng nhau, đầu mình thường sẽ như thế này:
Khoan.
- current đang ở đâu?
- next có bị mất không?
- Mũi tên nào vừa thay đổi?
- prev đang trỏ tới đâu?
😿
Nếu xem runtime step-by-step, chúng ta có thể thực sự thấy các pointer di chuyển.
prev current
↓ ↓
null 1 → 2 → 3
↓↓↓
null ← 1 2 → 3
↑ ↑
prev current
↓↓↓
null ← 1 ← 2 3
↑ ↑
prev current
↓↓↓
null ← 1 ← 2 ← 3
↑
prev
Nhìn như vậy, algorithm trở nên đơn giản hơn nhiều so với việc nghĩ về “bốn assignment bí ẩn”.
Thực tế nó chỉ là:
Lưu next
↓
Reverse mũi tên
↓
Di chuyển prev
↓
Di chuyển current
↓
Lặp lại
Chỉ vậy thôi.
Nice! 🔗😸
🌳 Maximum Depth of Binary Tree
Cuối cùng, hãy xem một tree.
Giả sử có binary tree này:
3
/ \
9 20
/ \
15 7
Maximum depth của tree này là bao nhiêu?
Path dài nhất từ root tới leaf có ba nodes:
3
↓
20
↓
15
Vậy đáp án là:
3
Làm sao để tính được nó?
Hãy nghĩ về một Tree nhỏ hơn
Giả sử chúng ta đang đứng ở một node.
Không cần hiểu toàn bộ tree cùng lúc.
Chỉ cần hỏi:
Depth của left subtree là bao nhiêu?
Depth của right subtree là bao nhiêu?
Sau đó chọn cái lớn hơn.
Cuối cùng cộng thêm 1 cho node hiện tại.
Đó chính xác là điều implementation này làm:
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;
}
Idea quan trọng nhất là:
Math.max(leftDepth, rightDepth) + 1;
Nhưng recursion lúc đầu có thể khá khó hiểu.
Ví dụ khi gọi:
maxDepth(root.left);
thì function đang chạy trước đó đi đâu?
Và làm thế nào tất cả các lần gọi maxDepth cuối cùng lại trở thành một number?
Hãy xem một example nhỏ.
1
/ \
2 3
/
4
Bắt đầu ở:
1
Nhưng node 1 chưa thể biết depth của mình.
Trước tiên nó hỏi left child:
maxDepth(2)
Node 2 lại tiếp tục hỏi:
maxDepth(4)
Node 4 không có children.
Vì vậy cả hai bên cuối cùng đều đi tới:
null
Và:
maxDepth(null);
trả về:
0
Bây giờ node 4 có thể tính:
max(0, 0) + 1
= 1
Sau đó quay lại node 2.
left side có depth:
1
right side là null:
0
Nên:
max(1, 0) + 1
= 2
Tiếp tục quay lại node 1.
Cuối cùng right subtree cũng trả về:
1
Vậy node 1 nhận được:
leftDepth = 2
rightDepth = 1
Và tính:
max(2, 1) + 1
= 3
Đáp án:
3
🎉
Điều thú vị là: đi xuống rồi quay lại
Đây là một trong những điều mình thấy thú vị nhất về recursion.
Các function call trước tiên đi xuống tree.
1
↓
2
↓
4
↓
null
Nhưng answer thật sự được xây dựng khi chúng ta quay trở lại.
null → 0
4 → 1
2 → 2
1 → 3
Vậy recursion không chỉ đơn giản là:
Gọi cùng một function nhiều lần.
Thực tế có hai hướng:
Đi xuống
↓
Đến base case
↓
Trả return value ngược lên trên
Base case ở đây là:
if (root === null) {
return 0;
}
Nếu không có nó, recursion sẽ không có nơi để dừng.
Complexity
Mỗi node được visit đúng một lần.
Time: O(n)
Kích thước recursive call stack phụ thuộc vào height của tree.
Space: O(h)
Trong đó h là height của tree.
Nếu tree balanced, nó khoảng:
O(log n)
Trong worst case, nếu tree trông giống linked list:
1
\
2
\
3
\
4
thì call stack có thể lên tới:
O(n)
👀 Hãy View View nó
Recursion có lẽ là một trong những example mình thích visualization nhất.
Vì final implementation rất ngắn:
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
Nhưng có rất nhiều thứ bị ẩn bên trong các function call này.
Nếu chỉ đọc code, đôi khi cảm giác giống như:
maxDepth()
inside maxDepth()
inside maxDepth()
inside maxDepth()
...
Bây giờ mình đang ở đâu vậy??? 😿
Nếu theo dõi execution step-by-step, chúng ta có thể thấy cả hai hướng.
Đầu tiên là đi xuống:
Going down
1
↓
2
↓
4
↓
null
Sau đó quay trở lại:
Coming back
null → 0
↓
4 → 1
↓
2 → 2
↓
1 → 3
Nhìn như thế này giúp recursion trở nên dễ hiểu hơn rất nhiều.
Hỏi các subproblem nhỏ hơn để lấy answer, rồi dùng những answer đó để xây dựng answer hiện tại.
🌳😸
🧠 Cuối cùng chúng ta đã học được gì?
Ba bài toán này nhìn hoàn toàn khác nhau.
Nhưng mỗi bài đều dạy một cách suy nghĩ rất hữu ích.
Valid Parentheses
Nếu item được thêm gần nhất cần được xử lý trước, hãy nghĩ tới stack.
Thứ cuối cùng mình mở là gì?
Reverse Linked List
Khi thay đổi reference, hãy lưu những gì còn cần dùng trước khi phá connection cũ.
Trước khi đổi pointer này, bước tiếp theo mình cần đi đâu?
Maximum Depth of Binary Tree
Chia bài toán thành những bài toán nhỏ hơn nhưng có cùng hình dạng.
Mình có thể lấy answer từ children rồi xây dựng answer của mình không?
Đây cũng là một lý do mình thấy học ba bài này cùng nhau khá thú vị.
implementation của chúng đều không dài.
Nhưng mental model phía sau lại hoàn toàn khác nhau:
Stack
Pointer
Recursion
Và nhiều khi, hiểu mental model còn khó hơn học syntax.
Đọc code có thể cho chúng ta biết điều gì xảy ra.
Nhưng mình cũng muốn thấy:
Nó xảy ra như thế nào.
Mình muốn View View. 👀👀
🎯 Kết luận
Trong bài này, chúng ta đã xem:
- Valid Parentheses với stack
- Reverse Linked List với pointer manipulation
- Maximum Depth of Binary Tree với recursion
Và quan trọng nhất, chúng ta đã theo dõi state thay đổi như thế nào trong lúc mỗi algorithm chạy.
Ở Valid Parentheses, chúng ta thấy:
stack.push() / stack.pop()
thay đổi stack ra sao.
Ở Reverse Linked List, chúng ta thấy:
prev
current
next
di chuyển từng bước như thế nào.
Và ở binary tree, chúng ta thấy recursive calls đi xuống tree rồi mang answer quay ngược trở lại.
Đó chính là lý do mình tạo DSA View View.
https://dsa-view-view.vercel.app
Bạn có thể tự viết hoặc load một TypeScript implementation, chạy nó với input của riêng mình, rồi di chuyển backward / forward trong runtime để kiểm tra từng step.
Nếu bạn cũng đang học DSA, hãy thử View View một trong những bài trên.
Đặc biệt khi bạn có cảm giác:
Mình hiểu từng dòng riêng lẻ... nhưng không hiểu vì sao ghép lại thì cả bài lại khó hiểu như vậy. 😿
Nhìn trực tiếp runtime có thể giúp những phần rời rạc đó kết nối lại với nhau.
Nếu có bài DSA nào bạn muốn mình viết tiếp, hãy để lại comment nhé!
Mình cũng còn rất nhiều algorithm muốn học. 😸
Cùng luyện cơ DSA thôi! 💪
Nếu bạn thích DSA View View, hãy cho project một star ⭐
https://github.com/nyaomaru/dsa-view-view
Hẹn gặp lại ở bài tiếp theo!
Bản tiếng Anh gốc:
https://dev.to/nyaomaru/learn-valid-parentheses-reverse-linked-list-and-tree-max-depth-with-step-by-step-visualization-in-3o09
All rights reserved
