leetcode刷题之广度搜索
2022-06-30 本文已影响0人
sk邵楷
1, 相同的树—— 0100 广度搜索 深度搜索
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
import collections
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
#深度搜索
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
elif not p or not q:
return False
elif p.val != q.val:
return False
else:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
#广度搜索
class Solution2:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if not p or not q:
return False
queue1 = collections.deque([p])
queue2 = collections.deque([q])
while queue1 and queue2:
node1 = queue1.popleft()
node2 = queue2.popleft()
if node1.val != node2.val:
return False
left1, right1 = node1.left, node1.right
left2, right2 = node2.left, node2.right
if (not left1) ^ (not left2):
return False
if (not right1) ^ (not right2):
return False
if left1:
queue1.append(left1)
if right1:
queue1.append(right1)
if left2:
queue2.append(left2)
if right2:
queue2.append(right2)
return not queue1 and not queue2
p = TreeNode(1)
q = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(2)
e = TreeNode(3)
p.left = b
p.right = c
q.left = d
q.right = e
S = Solution()
print(S.isSameTree(p, q))
S2 = Solution2()
print(S2.isSameTree(p, q))
2, 对称二叉树—— 101 递归 迭代
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3]
输出：true
from typing import Optional
import collections
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root.left and not root.right:
return True
if not root.left or not root.right:
return False
p, q = root.left, root.right
def dfs(p, q):
if not p and not q:
return True
if (not p or not q) or p.val != q.val:
return False
return dfs(p.left, q.right) and dfs(p.right, q.left)
return dfs(p, q)
#改造为迭代
class Solution2:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root.left and not root.right:
return True
if not root.left or not root.right:
return False
p, q = root.left, root.right
def check(p, q):
queue1 = collections.deque()
queue1.append(p)
queue1.append(q)
while queue1:
node1 = queue1.popleft()
node2 = queue1.popleft()
if not node1 and not node2:
continue
if (not node1 or not node2) or node1.val != node2.val:
return False
queue1.append(node1.left)
queue1.append(node2.right)
queue1.append(node1.right)
queue1.append(node2.left)
return True
return check(p, q)
root = TreeNode(1)
a1 = TreeNode(2)
a2 = TreeNode(2)
a3 = TreeNode(3)
a4 = TreeNode(4)
a5 = TreeNode(4)
a6 = TreeNode(3)
root.left = a1
root.right = a2
a1.left = a3
a1.right = a4
a2.left = a5
a2.right = a6
S = Solution()
print(S.isSymmetric(root))
S2 = Solution2()
print(S2.isSymmetric(root))
3, 二叉树的层序遍历—— 102 广度搜索
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
from typing import List
from collections import deque
# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
que = deque()
que.append(root)
while que:
size = len(que)
level = []
for _ in range(size):
node = que.popleft()
level.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(level)
return res
root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.levelOrder(root))
4, 二叉树的最大深度—— 104 广度搜索
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]， 返回它的最大深度 3 。
from typing import List
from collections import deque
from typing import Optional
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
que = deque()
high = 0
que.append(root)
while que:
size = len(que)
for _ in range(size):
node = que.popleft()
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
high += 1
return high
root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.maxDepth(root))
5, 二叉树的层序遍历 II —— 107 广度遍历
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
from typing import List
from collections import deque
# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = list()
que = deque()
que.append(root)
while que:
size = len(que)
level = list()
for _ in range(size):
node = que.popleft()
level.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
res.append(level)
# return res[::-1]
res.reverse()
return res
root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.levelOrderBottom(root))
6, 二叉树的最小深度—— 111 广度遍历
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
from typing import List
from collections import deque
# 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 minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
que = deque()
que.append(root)
res = 0
while que:
size = len(que)
res = res + 1
for _ in range(size):
node = que.popleft()
if not node.left and not node.right:
return res
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
root = TreeNode(3)
a1 = TreeNode(9)
a2 = TreeNode(20)
a3 = TreeNode(15)
a4 = TreeNode(7)
root.left = a1
root.right = a2
a2.left = a3
a2.right = a4
S = Solution()
print(S.minDepth(root))
7, 路径总和——112 递归 广度搜索
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
输入：root = [1,2,3], targetSum = 5
输出：false
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
from typing import List
from collections import deque
from typing import Optional
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
if targetSum == root.val:
return True
else:
return False
return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)
# 广度搜索
def hasPathSum2(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
que = deque()
que.append(root)
que2 = deque()
que2.append(root.val)
while que:
size = len(que)
for _ in range(size):
node = que.popleft()
sum = que2.popleft()
if not node.left and not node.right:
if sum == targetSum:
return True
if node.left:
que.append(node.left)
que2.append(sum+node.left.val)
if node.right:
que.append(node.right)
que2.append(sum + node.right.val)
return False
root = TreeNode(1)
a1 = TreeNode(2)
a2 = TreeNode(3)
root.left = a1
root.right = a2
S = Solution()
print(S.hasPathSum(root, 3))
S = Solution()
print(S.hasPathSum2(root, 5))
