Python | Leetcode刷题日寄Part05

欢迎交流学习~~

---

LeetCode & Python 系列：

🏆 Python | Leetcode刷题日寄Part01
🔎 Python | Leetcode刷题日寄Part02
💝 Python | Leetcode刷题日寄Part03
✈️ Python | Leetcode刷题日寄Part04

---

💦：二叉树的中序遍历

题目描述：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例：

输入：root = [1,null,2,3]
输出：[1,3,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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []return self.inorderTraversal(root.left) +  [root.val] + self.inorderTraversal(root.right)

---

🔥：对称二叉树

题目描述：
给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例：

输入：root = [1,2,2,3,4,4,3]
输出：true

题解：

# 递归
class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truereturn self.compare(root.left, root.right)def compare(self, left, right):# 首先排除空节点的情况if left == None and right != None: return Falseelif left != None and right == None: return Falseelif left == None and right == None: return True# 排除了空节点，再排除数值不相同的情况elif left.val != right.val: return False# 此时就是：左右节点都不为空，且数值相同的情况# 此时才做递归，做下一层的判断# 左子树：左、 右子树：右outside = self.compare(left.left, right.right)# 左子树：右、 右子树：左inside = self.compare(left.right, right.left)# 左子树：中、 右子树：中 （逻辑处理）isSame = outside and inside 				return isSame

---

🍞：翻转二叉树

题目描述：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root: return roottemp = root.leftroot.left = self.invertTree(root.right)root.right = self.invertTree(temp)return root

---

💡：验证二叉搜索树

题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例：

输入：root = [2,1,3]
输出：true

题解：

# 递归
# 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 isValidBST(self, root: TreeNode) -> bool:self.pre = Nonedef isBST(root):if not root:return Trueif not isBST(root.left):return Falseif self.pre and self.pre.val >= root.val:return Falseself.pre = root#print(root.val)return  isBST(root.right)return isBST(root)       

---

🚀：岛屿数量

题目描述：
给你一个由 1（陆地）和 0（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例：
输入：

grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]

输出：1

题解：

# 递归，dfs
class Solution:def dfs(self, grid, r, c):grid[r][c] = 0nr, nc = len(grid), len(grid[0])for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":self.dfs(grid, x, y)def numIslands(self, grid: List[List[str]]) -> int:nr = len(grid)if nr == 0:return 0nc = len(grid[0])num_islands = 0for r in range(nr):for c in range(nc):if grid[r][c] == "1":num_islands += 1self.dfs(grid, r, c)return num_islands

---

🌲：二叉树的最小深度

题目描述：
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例：

输入：root = [3,9,20,null,null,15,7]
输出：2

题解：

# 递归，dfs
# 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 0if not root.left and not root.right:return 1min_depth = 10**9if root.left:min_depth = min(self.minDepth(root.left), min_depth)if root.right:min_depth = min(self.minDepth(root.right), min_depth)return min_depth + 1

---

🎁：二叉树展开为链表

题目描述：
给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

题解：

# 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 = rightclass Solution:def flatten(self, root):while root:if root.left:   			# 左子树存在的话才进行操作sub_left = root.leftwhile sub_left.right:   # 左子树的右子树找到最深sub_left = sub_left.rightsub_left.right = root.right # 将root的右子树挂到左子树的右子树的最深root.right = root.left      # 将root的左子树挂到右子树root.left = None            # 将root左子树清空root = root.right               # 继续下一个节点的操作

---

🌞：二叉树的前序遍历

题目描述：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例：

输入：root = [1,null,2,3]
输出：[1,2,3]

题解：

# 递归
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

---

🌠：相同的树

题目描述：
给你两棵二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例：

输入：p = [1,2,3], q = [1,2,3]
输出：true

题解：

# 递归
# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:if not p and not q: return Trueelif not p or not q: return Falseelif p.val != q.val: return Falsereturn self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

---

💎：路径总和

题目描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

题解：

# 递归
# 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:# 如果树为空，返回 Falseif root == None:return False# 如果当前节点为叶子节点，且叶子节点的值等于减去该路径之前节点的值，返回 Trueif root.left == None and root.right == None and root.val == targetSum:return True# 递归左子树leftPath = self.hasPathSum(root.left, targetSum - root.val)# 递归右子树rightPath = self.hasPathSum(root.right, targetSum - root.val)return leftPath or rightPath

---