栈总结
概要
-
特点:Last In First Out,后入先出。(图来自 LeetCode 官方)
- 操作:
-
入栈(push) :也叫插入(insert),新元素会被添加至栈顶;
-
出栈(pop) :也叫删除(delete),只能移除栈顶元素。
-
- 应用:
-
「树的前、中、后序遍历」
-
「图的 DFS」,以上二者的特点:不达到最深的节点,就不回溯。DFS 因为要回溯,每次回溯的是最深的节点,也就是后进入的节点,这符合后入先出的特性。
-
递归:递归的调用栈,在某些时候,递归可以改写成栈的形式
-
-
DFS VS BFS
DFS BFS 最常使用 栈 队列 更早访问的结点可能不是更靠近根结点的结点 擅长找最短路径
模板
1. DFS 的递归模板
类似于回溯模板
改写自 LeetCode 官方 Java 模板
def dfs(cur, target, visited):
if cur is target:
return True
for next in neighbors of cur:
if next not in visited:
visited.add(next)
return True if dfs(next, target, visited)
return False
2. DFS 的循环模板
将递归改写成「循环+栈」的形式
改写自 LeetCode 官方 Java 模板
def dfs(root, target):
stack = [root]
while stack:
cur = stack.pop()
if cur is target:
return True
for next in neighbors of cur:
if next not in visited:
stack.append(next)
visited.add(next)
return False
相关题目
No | Problem | Difficulty | Link | Solution | Comment |
---|---|---|---|---|---|
94 | 二叉树的中序遍历 | 中等 | 题目 | 题解 | 中序遍历的栈的实现 |
133 | 克隆图 | 中等 | 题目 | 题解 | 图遍历的 DFS、BFS 解法 |
150 | 逆波兰表达式求值 | 中等 | 题目 | 题解 | 栈的经典应用 |
200 | 岛屿数量 | 中等 | 题目 | 题解 | DFS + 递归的解法 |
200 | 岛屿数量 | 中等 | 题目 | 题解 | DFS + 栈的解法 |
494 | 目标和 | 中等 | 题目 | 题解 | 回溯 + 备忘录 |
739 | 每日温度 | 中等 | 题目 | 题解 | 栈的经典题目 |
841 | 钥匙和房间 | 中等 | 题目 | 题解 | 没有明显的终止条件的 DFS 递归,也可改写成循环 + 队列的形式 |
留下评论