BÀI VIẾT
Ghi chép về xây dựng và vận hành hệ thống
Bài kỹ thuật — kiến trúc, bảo mật, và đôi khi là chuyện chiến trường.
#dfs · Tất cả bài viết
Series
Thẻ
- #leetcode 50
- #array 13
- #dfs 11
- #recursion 10
- #bfs 9
- #dynamic-programming 9
- #arrays 7
- #hash-table 7
- #trees 7
- #binary-search 6
- #two-pointers 6
- #string 5
- #backtracking 4
- #dp 4
- #graphs 4
- #greedy 4
- #matrix 4
- #sliding-window 4
- #hash-map 3
- #heap-priority-queue 3
- #linked-list 3
- #binary-search-tree 2
- #heap 2
- #math 2
- #memoization 2
- #priority-queue 2
- #sorting 2
- #stack 2
- #strings 2
- #binary-tree 1
- #bit-manipulation 1
- #bucket-sort 1
- #counting 1
- #cycle-detection 1
- #divide-and-conquer 1
- #geometry 1
- #kadane 1
- #multi-source-bfs 1
- #prefix-sum 1
- #quickselect 1
- #simulation 1
- #string-matching 1
- #topological-sort 1
- #union-find 1
01
Clone Graph: sao chép sâu một cấu trúc đồ thị có chu trình
Clone một đồ thị nghĩa là tạo ra một bản sao hoàn toàn độc lập — nhưng đồ thị có chu trình, nên nếu duyệt đệ quy thuần túy thì sẽ lặp vô hạn. Giải pháp gọn nhất là một hash map và một quy tắc về thứ tự đăng ký clone.14 thg 6, 2026 · 10 phút đọc · #00046
02
Validate Binary Search Tree: tại sao chỉ kiểm tra node cha là sai
Lỗi cổ điển nhất là so sánh một node chỉ với node cha trực tiếp. BST hợp lệ yêu cầu ràng buộc thứ tự toàn cục truyền xuống toàn bộ subtree — và cách sạch nhất để thể hiện điều này là mang theo các bounds hợp lệ qua từng lần gọi recursion.14 thg 6, 2026 · 11 phút đọc · #00035
03
Same Tree: hai cây, một câu hỏi đệ quy
Kiểm tra xem hai binary tree có giống hệt nhau hay không quy về một câu hỏi đệ quy duy nhất tại mỗi cặp node. Giải pháp DFS chỉ cần ba base case và một câu lệnh return. Nhưng BFS — xử lý hai cây theo từng level trong cùng một queue — cũng đáng hiểu, và các edge case ẩn chứa một vài chi tiết dễ nhầm.14 thg 6, 2026 · 11 phút đọc · #00033
04
Number of Islands: flood-fill, BFS, và khi nào Union-Find mới thực sự xứng đáng
LeetCode 200 yêu cầu đếm số đảo trong một lưới nhị phân. Ba cách tiếp cận — DFS flood-fill, BFS, và Union-Find — đều ra kết quả đúng, nhưng constraints cho bạn biết chính xác nên dùng cái nào và tại sao.14 thg 6, 2026 · 13 phút đọc · #00045
05
Permutations: xây dựng mọi thứ tự bằng backtracking
LeetCode 46 là bài nhập môn backtracking rõ ràng nhất — ba cách tiếp cận từ một dòng lệnh thư viện đến swap tại chỗ, mỗi cách để lộ thêm một góc nhìn về cách suy nghĩ khi giải bài toán liệt kê.14 thg 6, 2026 · 12 phút đọc · #00043
06
Course Schedule: phát hiện chu trình là toàn bộ bài toán
LeetCode 207 trông như bài toán lập lịch học nhưng thực chất là hỏi liệu đồ thị có hướng có chứa chu trình hay không. Khi nhìn thấy điều đó, hai giải pháp rõ ràng hiện ra — DFS ba màu và Kahn's BFS topological sort — cùng chạy O(V+E), khác nhau ở chỗ bạn có cần thứ tự sắp xếp sau này không.14 thg 6, 2026 · 13 phút đọc · #00047
07
Phần tử nhỏ thứ K trong BST: in-order traversal như một dòng dữ liệu đã sắp xếp
In-order traversal trên BST cho ra các node theo thứ tự tăng dần. Để tìm phần tử nhỏ thứ k, bạn không cần thu thập tất cả — chỉ cần dừng đúng lúc chạm đến node thứ k. Điều đó vừa đủ, vừa đúng.14 thg 6, 2026 · 11 phút đọc · #00036
08
Word Search: DFS backtracking đánh dấu và xoá dấu trên chính đường đi của mình
LeetCode 79 là lúc backtracking ngừng là khái niệm trừu tượng — grid bắt bạn phải theo dõi chính xác những ô nào đang nằm trên đường đi hiện tại, hoàn tác trạng thái đó khi gặp ngõ cụt, và khởi động lại sạch. Hai giải pháp hoàn chỉnh cho thấy một phép biến đổi in-place thay thế được toàn bộ một ma trận visited.14 thg 6, 2026 · 16 phút đọc · #00044
09
Subtree of Another Tree: khi Same Tree trở thành bài toán con
LeetCode 572 hỏi liệu một cây nhị phân có xuất hiện dưới dạng subtree liên thông trong một cây khác không. Giải pháp DFS brute-force tái sử dụng hàm kiểm tra Same Tree từ bài 100 — gọn và đủ với ràng buộc đề cho. Cách tiếp cận serialize thành string cắt giảm chi phí asymptotic nhưng có một bẫy correctness quan trọng mà hầu hết implementation đều bỏ qua.14 thg 6, 2026 · 11 phút đọc · #00034
10
Invert Binary Tree: recursion là sự phù hợp tự nhiên
Đảo ngược binary tree là một trong những bài toán mà giải pháp đệ quy tự viết khi bạn nhìn thấy nó: hoán đổi các con, sau đó đệ quy vào mỗi cái. Phiên bản iterative với queue cũng hoạt động — chỉ là ít rõ ràng hơn tại sao bạn lại dùng nó ở đây.13 thg 6, 2026 · 12 phút đọc · #00030
11
Maximum Depth of Binary Tree: chiều cao như một tính toán post-order
Chiều sâu của một cây bằng 1 cộng với chiều sâu tối đa của các cây con của nó. Đó là post-order traversal: xử lý con trước cha. Có ba cách tiếp cận — đệ quy (gọn nhất), iterative DFS với stack (cùng traversal, cơ chế khác), và BFS nơi chiều sâu bằng với số lượng level.13 thg 6, 2026 · 12 phút đọc · #00031
Đôi dòng ghi chép về những gì tôi đang xây
Nhận email khi tôi đăng bài mới — các bài kỹ thuật, không spam. Hủy đăng ký bất cứ lúc nào.