深度优先搜索和广度优先搜索数道习题
在树这一块我真的很发怵，我一直在思考我如何如何地畏惧它、怕它，其实我应该思考如何记住它、使用它，所以我搜集了在LC上三个多月的每日一题，这里将针对其中的七道题进行一个归纳总结，深度优先搜索（DFS）以及广度优先搜索（BFS）。
每道题的解法一是这两种算法中优先选用的或最容易想到的，解法二则是为了将两种算法给补足。
1302. 层数最深叶子节点的和 *
题目链接：1302. 层数最深叶子节点的和
题目大意：计算一棵二叉树的层数最深的叶子节点的和 。
解法（一）广度优先搜索 这是一个典型的模板，主要就是构建双端队列以及双循环。
- q = deque([root])
- while的大循环，用以决定是否已经走到了属的最底层；for的内循环，用来对每一层结点进行操作，并为下一层做准备。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
# BFS
q = deque([root])
while q:
ans = 0
size = len(q)
for _ in range(size):
node = q.popleft()
ans += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans
''''''
解法（二）深度优先搜索 典型的递归结构，可以更好地控制树的层数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
# DFS
maxLevel,ans = -1,0
def dfs(node:Optional[TreeNode],level:int) -> None:
if node is None:
return
nonlocal maxLevel,ans
if level > maxLevel:
maxLevel,ans = level,node.val
elif level == maxLevel:
ans += node.val
dfs(node.left,level+1)
dfs(node.right,level+1)
dfs(root,0)
return ans
623. 在二叉树中增加一行
题目链接：1302. 层数最深叶子节点的和
题目大意：给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。注意，根节点 root 位于深度 1 。
加法规则如下:
- 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
- cur 原来的左子树应该是新的左子树根的左子树；cur 原来的右子树应该是新的右子树根的右子树。
- 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
解法（一）深度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
# DFS
if root is None: return
if depth == 1:
return TreeNode(val,root,None)
if depth == 2:
root.left = TreeNode(val,root.left,None)
root.right = TreeNode(val,None,root.right)
else:
root.left = self.addOneRow(root.left,val,depth-1)
root.right = self.addOneRow(root.right,val,depth-1)
return root
解法（二）广度优先搜索 其实不太适合，for 循环就是为了到达需要的层，有些浪费。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
# BFS
if depth == 1:
return TreeNode(val,root,None)
cur = [root]
for __ in range(1,depth-1):
tmp = []
for node in cur:
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
cur = tmp
for node in cur:
node.left = TreeNode(val,node.left,None)
node.right = TreeNode(val,None,node.right)
return root
513. 找树左下角的值
题目链接：513. 找树左下角的值
题目大意：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
解法（一）广度优先搜索 这个比较好用，走到最后一层要最左边就OK！这里面 q.append 的顺序有必要好好想一想。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
q = deque([root])
while q:
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
ans = node.val
return ans
解法（二）深度优先搜索 if height > curHeight时，curHeight = height 防止后续 curVal 被修改。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
curVal,curHeight = 0,0
def dfs(node: Optional[TreeNode],height:int) -> None:
if node is None: return
height += 1
dfs(node.left,height)
dfs(node.right,height)
nonlocal curVal,curHeight
if height > curHeight:
curHeight = height
curVal = node.val
dfs(root,0)
return curVal
1022. 从根到叶的二进制数之和
题目链接：1022. 从根到叶的二进制数之和
题目大意：给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
- 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
- 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
- 返回这些数字之和。题目数据保证答案是一个 32 位 整数。
解法（一） 深度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode],val: int) -> int:
if node is None: return 0
val = (val << 1) | node.val
if node.left is None and node.right is None: return val
return dfs(node.left,val) + dfs(node.right,val)
return dfs(root,0)
解法（二）广度优先搜索 不好用啊
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
ans=val=0
st = []
pre = None
while root or st:
while root:
val = (val<<1) | root.val
st.append(root)
root = root.left
root = st[-1]
if root.right is None or root.right == pre:
if root.left is None and root.right is None:
ans += val
val >>= 1
st.pop()
pre = root
root = None
else:
root = root.right
return ans
310. 最小高度树
题目链接：5310. 最小高度树
题目大意：树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
- 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
- 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
- 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
解法（一） 广度优先搜索
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# First, find maxlength path
# Second, find the degree of node > 2
if n == 1:
return [0]
g = [[] for _ in range(n)]
deg = [0] * n
for x,y in edges:
g[x].append(y)
g[y].append(x)
deg[x] += 1
deg[y] += 1
q = [i for i,d in enumerate(deg) if d == 1]
remainNodes = n
while remainNodes > 2:
remainNodes -= len(q)
tmp = q
q = []
for x in tmp:
for y in g[x]:
deg[y] -= 1
if deg[y] == 1:
q.append(y)
return q
解法（二） 深度优先搜索
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
parents = [0] * n
maxDepth, node = 0, -1
def dfs(x: int, pa: int, depth: int):
nonlocal maxDepth, node
if depth > maxDepth:
maxDepth, node = depth, x
parents[x] = pa
for y in g[x]:
if y != pa:
dfs(y, x, depth + 1)
dfs(0, -1, 1)
maxDepth = 0
dfs(node, -1, 1)
path = []
while node != -1:
path.append(node)
node = parents[node]
m = len(path)
return [path[m // 2]] if m % 2 else [path[m // 2 - 1], path[m // 2]]
429. N 叉树的层序遍历 *
题目链接：429. N 叉树的层序遍历
题目大意：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔。
解法（一） 广度优先搜索 好用啊
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if root is None: return
res = []
queue = collections.deque([root])
while queue:
tmp = []
size = len(queue)
for _ in range(size):
cur = queue.popleft()
tmp.append(cur.val)
for child in cur.children:
queue.append(child)
res.append(tmp)
return res
解法（二） 深度优先搜索
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
res = []
def dfs(root: 'Node',level: int) -> None:
if root is None: return
if len(res) == level:
res.append([])
res[level].append(root.val)
for node in root.children:
dfs(node,level+1)
dfs(root,0)
return res
606. 根据二叉树创建字符串
题目链接：606. 根据二叉树创建字符串
题目大意：给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。空节点使用一对空括号对 “()” 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
解题（一）深度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# care for reading title, this question is for a node
def tree2str(self, root: Optional[TreeNode]) -> str:
ans = ""
if root is None: return ""
ans += str(root.val)
if root.left:
ans += f"({self.tree2str(root.left)})"
if root.right:
if root.left is None:
ans += '()'
ans += f"({self.tree2str(root.right)})"
return ans
解题（二）广度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
ans = ""
st = [root]
vis = set()
while st:
node = st[-1]
if node in vis:
if node != root:
ans += ')'
st.pop()
else:
vis.add(node)
if node != root:
ans += '('
ans += str(node.val)
if node.left is None and node.right:
ans += '()'
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
return ans
662. 二叉树最大宽度 *
题目链接：662. 二叉树最大宽度
题目大意：给你一棵二叉树的根节点 root ，返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。题目数据保证答案将会在 32 位 带符号整数范围内。
- 解法（一） 广度优先搜索 这道题的关键就是找到各层的最左及最右的节点位置，需要使用传统的一个数组编号，即：
- 左子树的结点编号为 index2；右子树则为 index2+1
- 学习 这种二维数组的创建
q =[[root,1]]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# BFS
ans = 1
q =[[root,1]]
while q:
tmp = []
for node,index in q:
if node.left:
tmp.append([node.left,index*2])
if node.right:
tmp.append([node.right,index*2+1])
ans = max(ans,q[-1][1] - q[0][1] + 1)
q = tmp
return ans
解法（二） 深度优先搜索 相较于BFS慢一些 不过更好理解，思路于BFS的方法一致，注意比较两种方法在编写中的不同点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# DFS
levelLeft = {}
def DFS(node: Optional[TreeNode],depth: int,index: int) -> int:
if node is None: return 0
if depth not in levelLeft:
levelLeft[depth] = index
return max(index - levelLeft[depth]+1,
DFS(node.left,depth+1,index*2),
DFS(node.right,depth+1,index*2+1))
return DFS(root,1,1)
695. 岛屿的最大面积
题目链接：695. 岛屿的最大面积
题目大意： 给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
（一）深度优先算法 好理解 稍微慢一些
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
# DFS
m,n = len(grid),len(grid[0])
def DFS(i: int,j: int) -> int:
if 0<=i<m and 0<=j<n and grid[i][j]:
grid[i][j] = 0
# 上下左右
return 1 + DFS(i-1,j) + DFS(i+1,j) + DFS(i,j-1) + DFS(i,j+1)
return 0
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j]:
ans = max(ans,DFS(i,j))
return ans
（二）广度优先算法 快 但是不是很好编写
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
# BFS
def BFS(i: int,j: int) -> int:
q = [(i,j)]
grid[i][j] = 0
tmp = 1
while q:
x,y = q.pop()
for dx,dy in directions:
nx,ny = x+dx,y+dy
if 0<=nx<m and 0<=ny<n and grid[nx][ny]:
grid[nx][ny] = 0
tmp += 1
q.append((nx,ny))
return tmp
669. 修剪二叉搜索树
题目链接：669. 修剪二叉搜索树
题目大意：给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
例如：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
（一）深度优先算法 好理解 稍微慢一些
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
# DFS
if root is None: return None
if root.val < low: return self.trimBST(root.right,low,high)
if root.val > high: return self.trimBST(root.left,low,high)
root.left = self.trimBST(root.left,low,high)
root.right = self.trimBST(root.right,low,high)
return root
（二）广度优先算法 快 但是不是很好编写
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
# BFS
while root and (root.val < low or root.val > high):
root = root.right if root.val < low else root.left
if root is None:
return None
node = root
while node.left:
if node.left.val < low:
node.left = node.left.right
else:
node = node.left
node = root
while node.right:
if node.right.val > high:
node.right = node.right.left
else:
node =node.right
return root
总结
明天要面试，这次我必须好好准备一下了，学习吧！今天凌晨记住尼采的一本书名，好长的，《查拉图斯特拉如是说》。我还看了一部分《三体：黑色森林（下部）》和《房思琪的初恋乐园》几章，说心里话看书真的可以让我放下好多没用的孤寂，无论怎么说，永远记住：我思故我在，努力地上进，努力地思考，努力地记忆，努力地努力。就这样吧，努力：奋斗！