DSA View View 可视化实战：岛屿数量、翻转二叉树与课程表
原文：https://dev.to/nyaomaru/learn-number-of-islands-invert-binary-tree-and-course-schedule-with-step-by-step-visualization-in-5947（作者 @nyaomaru）
DSA View View 通过可视化展示代码的实际运行过程，帮助你理解数据结构与算法（DSA）。
{% embed https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo %}
在之前的文章中，我们讨论过以下问题：
- Two Sum（两数之和）
- Binary Search（二分查找）
- Bubble Sort（冒泡排序）
- Valid Parentheses（有效括号）
- Reverse Linked List（反转链表）
- Maximum Depth of Binary Tree（二叉树的最大深度）
这次，我们来看另外三道经典题目：
- Number of Islands（岛屿数量）
- Invert Binary Tree（翻转二叉树）
- Course Schedule（课程表）
这三道题引入了一些非常有用的思维方式：
Explore connected things Transform a tree with recursion Resolve dependencies in the right order
这些问题的实现代码并不庞大。
但运行时的实际行为却可能复杂到难以在脑中推演。
所以让我们来看看实际发生了什么。
岛屿数量
我们从岛屿数量问题开始。
假设我们有这样一个网格：
1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0
1 表示陆地。
0 表示水域。
上下或左右相连的陆地属于同一个岛屿。
那么一共有多少个岛屿呢？
先看第一组。
1 1 1
这些格子是相连的。
所以它们构成了一个岛屿。
右边还有
1 1 1
这些格子也是相连的。
所以答案是 2。
很好！
但我们如何让代码理解多个 1 属于同一个岛屿呢？
找到一块陆地，然后探索所有相连的陆地
基本思路是：
当我们发现一个新的
1时，计数一个岛屿，然后访问所有与它相连的陆地。
我们用这个实现。
function numIslands(grid: string[][]): number {
let islands = 0;
const visit = (row: number, col: number): void => {
if (row < 0 || col < 0) return;
if (row >= grid.length || col >= grid[row].length) return;
if (grid[row][col] !== "1") return;
grid[row][col] = "0";
visit(row + 1, col);
visit(row - 1, col);
visit(row, col + 1);
visit(row, col - 1);
};
for (let row = 0; row < grid.length; row++) {
for (let col = 0; col < grid[row].length; col++) {
if (grid[row][col] === "1") {
islands++;
visit(row, col);
}
}
}
return islands;
}
有两个关键部分。
首先，我们扫描网格
for (let row = 0; row < grid.length; row++) {
for (let col = 0; col < grid[row].length; col++) {
然后，当我们发现陆地时
if (grid[row][col] === "1") {
islands++;
visit(row, col);
}
我们计数一个新的岛屿。
但接下来 visit() 做了一件重要的事。
它把与该岛屿相连的所有陆地从后续搜索中排除。
为什么要把 1 改成 0？
在 visit() 内部，我们有
grid[row][col] = "0";
乍一看，把陆地变成水域有点奇怪。
但在这里，0 的真正含义是
我们已经访问过这块陆地了。
我们来看一个小例子。
1 1 1 0
我们从左上角开始。发现了陆地！所以
islands = 1
然后
visit(0, 0);
在 visit() 内部，我们把它标记为已访问。
0 1 1 0
然后我们访问四个方向
down up right left
往下走发现了另一个 1。
0 1 1 0 ↑
所以我们也访问它。
0 1 0 0
从原始格子往右走也发现了陆地。
访问它。
0 0 0 0
现在，整个相连的岛屿已经从我们的搜索中消失了。
当外层循环继续时，那个岛屿中已经没有 1 可以再次计数了。
这就是核心思路。
计数一次，然后把整个相连区域标记为已访问。
为什么有四次递归调用？
我们使用
visit(row + 1, col); visit(row - 1, col); visit(row, col + 1); visit(row, col - 1);
意思是
up
↑
left ← current → right
↓
down
每个被访问的格子都会问
我旁边还有陆地吗？
每个新发现的陆地格子也会再次问同样的问题。
这个过程一直持续，直到我们遇到：
- 水域
- 网格边界外
- 已经访问过的陆地
这些情况会终止递归。
边界条件
这几行代码保护我们
if (row < 0 || col < 0) return; if (row >= grid.length || col >= grid[row].length) return; if (grid[row][col] !== "1") return;
所以，
- 如果走出了网格边界，停止。
- 如果遇到了水域，停止。
- 如果遇到了已经改成
0的格子，停止。
否则，继续探索。
跟踪两个岛屿
考虑这个网格
1 1 0 0 0 1 0 1 1
扫描从左上角开始。
1 1 0 ↑ 0 0 1 0 1 1
发现了陆地。
islands = 1
visit() 把所有与它相连的格子都清除掉。
0 0 0 0 0 1 0 1 1
循环继续。
最终我们到达
0 0 0
0 0 1
↑
0 1 1
又一个 1。
所以
islands = 2
visit() 探索整个相连区域。
0 0 0 0 0 0 0 0 0
完成！
2 islands
复杂度
每个格子最多被处理有限次。
如果网格有 m 行 n 列
Time: O(m × n)
在最坏情况下，递归调用栈可能随陆地格子的数量增长。
Space: O(m × n)
可视化看看
这是一种最终代码很简短的算法。
但在阅读时，有很多东西同时在变化
row col grid islands recursive calls
然后突然我们看到
grid[row][col] = "0";
- 为什么那个格子消失了？
- 我们当前在哪个递归调用中？
- 哪些格子属于当前岛屿？
- 递归结束后外层循环会从哪里继续？
要在脑海中模拟这些实在太多了。
当我们逐步查看时，思路会变得直观很多。
Find land ↓ islands++ ↓ visit connected land ↓ mark it visited ↓ expand up / down / left / right ↓ return to scanning ↓ find next island
与其先想递归，我更喜欢这样理解
找到一个岛屿，把整个岛屿涂掉，然后继续搜索。
翻转二叉树
接下来，我们来翻转一棵二叉树。
假设我们有
4
/ \
2 7
/ \ / \
1 3 6 9
我们想把它变成
4
/ \
7 2
/ \ / \
9 6 3 1
每个左子节点变成右子节点。
每个右子节点变成左子节点。
很简单，对吧？
嗯，最终的实现也出奇地简短。
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) return null;
const left = invertTree(root.left);
const right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
短得几乎有些可疑。
先往下走
我们用一棵更小的树来演示。
1 / \ 2 3
我们从节点 1 开始。
但我们不会立即交换。
首先，
const left = invertTree(root.left);
于是我们走到节点 2。
节点 2 也试图翻转它的左子节点。
但它没有子节点。
所以
if (root === null) return null;
返回 null。
节点 2 的右侧也是同样的情况。
现在节点 2 拥有
left = null right = null
所以
root.left = right; root.right = left;
不会产生任何可见的变化。
节点 2 返回。
然后节点 1 探索它的右子树。
3
节点 3 也没有子节点，经过同样的过程后返回。
直到这时我们才回到节点 1。
现在
left = 2 right = 3
然后我们执行
root.left = right; root.right = left;
于是
1 / \ 2 3
变成了
1 / \ 3 2
完成！
关键点：交换发生在回溯时
这正是递归解法有趣的地方。
函数先往下走。
1 ↓ 2 ↓ null
然后回溯。
之后它探索另一侧。
1 ↓ 3 ↓ null
当两个子节点都返回后，当前节点才交换它们。
所以整个流程更像是
向左走 ↓ 翻转左子树 ↓ 向右走 ↓ 翻转右子树 ↓ 交换返回的子树 ↓ 返回当前节点
树的变换是在递归回退的过程中逐步构建的。
一个稍大一点的例子
我们来看
4
/ \
2 7
/ \
1 3
我们从 4 开始。
invertTree(4)
然后
invertTree(2)
然后
invertTree(1)
节点 1 返回。
然后节点 3 返回。
现在节点 2 拥有
left = 1 right = 3
交换它们。
2 / \ 3 1
然后递归返回到 4。
以 7 为根的右子树也经历同样的处理。
最终节点 4 接收到
left = 以 2 为根的已翻转子树 right = 以 7 为根的已翻转子树
并交换它们。
最终的树变为
4
/ \
7 2
/ \
3 1
有趣之处在于，每个节点只需要了解它自己的两个子节点。
它不需要理解整棵树。
复杂度
我们访问每个节点一次。
时间：O(n)
递归调用栈的深度取决于树的高度。
空间：O(h)
对于平衡树
O(log n)
最坏情况下
O(n)
可视化查看
这正是递归难以在脑中模拟的地方。
代码写的是
const left = invertTree(root.left); const right = invertTree(root.right);
然后
root.left = right; root.right = left;
但我的大脑立刻开始追问：
- 我们现在说的是哪个 root？
- 节点 2 已经交换了吗？
- 我们还在往下走吗？
- 还是在往上回溯？
- 此刻 left 里装的是什么？
当我们逐步执行运行时，可以区分出两种不同的运动。
最终代码很短。
但实际运行时有一种节奏感。
向下走 ↓ 返回 ↓ 交换 ↓ 返回 ↓ 交换
一旦我能看到那种节奏，递归解法就不再那么神奇了。
课程表
最后，我们来看看课程表问题。
这道题稍微难一些。
假设有三门课程
0 1 2
先修课程关系是
[1, 0] [2, 1]
意思是
要修课程 1，先完成课程 0。 要修课程 2，先完成课程 1。
所以依赖关系是这样的
0 → 1 → 2
我们能修完所有课程吗？
能。
可以按 0 → 1 → 2 的顺序修。
很简单。
但如果依赖关系是这样的呢？
0 → 1 ↑ ↓ └── 2
现在
0 需要 2 1 需要 0 2 需要 1
每个课程都在等其他课程先完成。
永远无法开始。
这就是环。
如果存在环，就无法修完所有课程。
构建图
以下是实现代码：
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
const graph: number[][] = Array.from({ length: numCourses }, () => []);
const indegree: number[] = Array(numCourses).fill(0);
for (const [course, prerequisite] of prerequisites) {
graph[prerequisite].push(course);
indegree[course]++;
}
const queue: number[] = [];
for (let course = 0; course < numCourses; course++) {
if (indegree[course] === 0) queue.push(course);
}
let completed = 0;
for (let head = 0; head < queue.length; head++) {
const course = queue[head];
completed++;
for (const next of graph[course]) {
indegree[next]--;
if (indegree[next] === 0) queue.push(next);
}
}
return completed === numCourses;
}
这里有几个关键部分。
graph indegree queue completed
这正是那种每一行单独看都有道理的算法。
但整体看仍然可能让人困惑。
我们来拆解一下。
graph 是什么？
对于
0 → 1 → 2
我们想知道
修完这门课程后，哪些课程离可修更近了？
所以
graph[0] = [1] graph[1] = [2] graph[2] = []
意思是
完成 0 ↓ 课程 1 受影响 完成 1 ↓ 课程 2 受影响
我们在这里构建它
graph[prerequisite].push(course);
indegree 是什么？
indegree 告诉我们一门课程还在等几个先修课程。
对于
0 → 1 → 2
有
课程 0：0 个先修课程 课程 1：1 个先修课程 课程 2：1 个先修课程
所以
indegree = [0, 1, 1]
课程 0 比较特殊，因为它不需要任何前置课程。
所以可以直接从它开始。
从不需要前置课程的课程开始
我们构建队列
for (let course = 0; course < numCourses; course++) {
if (indegree[course] === 0) queue.push(course);
}
在我们的例子中
indegree = [0, 1, 1]
只有课程 0 的先修课程数为零。
所以
queue = [0]
这意味着
课程 0 当前可修。
完成课程 0
取
course = 0
然后
completed++;
所以
completed = 1
现在看看依赖 0 的课程。
graph[0] = [1]
课程 1 原本在等一个先修课程。
但课程 0 现在完成了。
所以
indegree[1]--;
然后
indegree[1] = 0
现在课程 1 不需要任何前置了。
把它加入队列。
queue = [0, 1]
完成课程 1
接下来
course = 1
现在
completed = 2
课程 2 依赖 1。
所以
indegree[2]: 1 → 0
把它加入队列。
queue = [0, 1, 2]
完成课程 2
最后
course = 2
所以
completed = 3
而
numCourses = 3
因此
completed === numCourses; // true
我们可以修完所有课程！
为什么这能检测环？
现在试试这个
0 → 1 ↑ ↓ └── 2
每门课程都有一个先修课程。
所以
indegree = [1, 1, 1]
我们尝试构建初始队列。
if (indegree[course] === 0)
但没有课程的入度为 0。
所以，什么都无法开始。
因此
completed = 0
而
0 === 3 // false
我们无法修完这些课程。
另一个例子
假设
0 → 2 1 → 2 2 → 3
课程 2 同时需要 0 和 1。
所以
indegree = [0, 0, 2, 1]
初始队列是
queue = [0, 1]
完成 0。
indegree[2]: 2 → 1
课程 2 还在等待。
先不加它。
完成 1。
indegree[2]: 1 → 0
现在课程 2 准备好了。
queue = [0, 1, 2]
完成 2。
indegree[3]: 1 → 0
现在
queue = [0, 1, 2, 3]
所有课程都能完成。
核心思路是
当一门课程的所有先修课程都完成后，该课程就变为可修。
为什么用 head 而不是 shift()？
队列是这样处理的
for (let head = 0; head < queue.length; head++) {
const course = queue[head]
而不是反复执行
queue.shift();
我们用一个索引指向下一个要处理的元素。
这样队列在遍历过程中可以继续增长。
例如
queue = [0] 处理 0 ↓ queue = [0, 1] 处理 1 ↓ queue = [0, 1, 2]
head 只是向前移动。
0 → 1 → 2 ↑ head
然后
0 → 1 → 2
↑
head
然后
0 → 1 → 2
↑
head
复杂度
V = 课程数量 E = 先修课程关系数量
我们构建一次图，然后处理每门课程和每条边。
时间：O(V + E) 空间：O(V + E)
来看看实际效果
这可能是三个可视化中最有趣的一个。
因为有多个东西在同时变化。
graph indegree queue head completed
如果我只读
indegree[next]--; if (indegree[next] === 0) queue.push(next);
我能理解语法。
但我可能还是会问：
- 为什么这门课现在变得可修了？
- 哪个前置条件被移除了？
- 为什么这门课还不在队列中？
- completed 告诉了我们什么？
- 环到底卡在哪里？
当我们查看运行时，可以观察到依赖逐渐消失。
0 → 1 → 2
indegree = [0, 1, 1]
queue = [0]
↓ finish 0
indegree = [0, 0, 1]
queue = [0, 1]
↓ finish 1
indegree = [0, 0, 0]
queue = [0, 1, 2]
↓ finish 2
completed = 3
代码不再像是神秘的簿记。
我们实际上在做一件简单的事：
不断取出已经准备好的课程，并让依赖它们的课程更接近就绪状态。
如果最终每门课都变得就绪
completed === numCourses
说明不存在阻塞的环。
如果有些课永远无法就绪
completed < numCourses
说明有东西卡在环里了。
我们到底学到了什么？
这三道题看起来截然不同。
但每道题都教会我们一种有用的思维方式。
岛屿数量
当你找到一个连通组的一部分时，先探索完整个组，再继续往下走。
还有哪些与它相连？
翻转二叉树
让递归调用先解决更小的子树，再用它们的结果来变换当前节点。
我的子节点能不能先完成它们的工作，然后我再改这个节点？
课程表
先处理那些没有未解决依赖的任务，再用它们来解锁更多工作。
现在有哪些可以安全处理？
这些实现都不算长。
但每道题都引入了不同的思维模型。
网格上的 DFS 递归树变换 拓扑排序
再次强调，语法并不是最难的部分。
最难的部分在于跟踪不断变化的状态。
- 我们在哪？
- 什么变了？
- 什么在等待？
- 哪些已经访问过了？
- 我们当前在哪个递归调用里？
有时候能读懂每一行代码，却在中途跟丢了线索。
这正是需要可视化查看的时候。
结论
在这篇文章中，我们探讨了：
- 用递归网格遍历解决岛屿数量
- 用递归解决翻转二叉树
- 用拓扑排序解决课程表
更重要的是，我们跟踪了每个算法运行时发生了什么变化。
对于岛屿数量，我们看着连通的陆地随着被访问而消失。
1 → 0
对于翻转二叉树，我们看着递归调用向下走，然后在返回时树发生变化。
向下 ↓ 返回 ↓ 交换
对于课程表，我们看着先修课程消失，新课程进入队列。
入度-- ↓ 0 个先修课程 ↓ queue.push()
这正是 DSA View View 这个工具的用途。
{% embed https://dsa-view-view.vercel.app %}
你可以编写或加载一个 TypeScript 实现，用自己的输入运行它，并在运行时前后逐步查看。
如果你也在学习 DSA，试试把其中一道题逐步可视化查看。
尤其是当实现看起来很短，但大脑仍然在说
等等……刚才什么变了？
看到运行时过程可能会让思路更容易跟上。
{% embed https://github.com/nyaomaru/dsa-view-view %}
原文：https://dev.to/nyaomaru/learn-number-of-islands-invert-binary-tree-and-course-schedule-with-step-by-step-visualization-in-5947（作者 @nyaomaru）