当前位置：首页 > news >正文

代码随想录算法训练营第51期第14天 | 226. 翻转二叉树、101. 对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度

news 来源：原创 2025/7/6 12:49:37

226. 翻转二叉树

226. 翻转二叉树https://leetcode.cn/problems/invert-binary-tree/1.昨天忘了声明，如果都用C的话，我大概率写不完，所以思路方面，我可能考虑用pyhon先写，后续会用文心一言转换成C

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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:if not root:return rootfrom collections import dequequeue = deque([root])while queue:node = queue.popleft()node.left, node.right = node.right, node.leftif node.left:queue.append(node.left)if node.right:queue.append(node.right)return rootclass Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:def traver(root):if not root:return Noneroot.left, root.right = root.right, root.lefttraver(root.left)traver(root.right)traver(root)return root

101. 对称二叉树

101. 对称二叉树https://leetcode.cn/problems/symmetric-tree/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 isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truefrom collections import dequequeue = deque()queue.append(root.left)queue.append(root.right)while queue:node1 = queue.popleft()node2 = queue.popleft()if not node1 and not node2:continueif not node1 or not node2 or node1.val != node2.val:return Falsequeue.append(node1.left)queue.append(node2.right)queue.append(node1.right)queue.append(node2.left)return True# 递归
class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:if not root:return Truereturn self.compare(root.left, root.right)def compare(self, left, right):if not left and right:return Falseif left and not right:return Falseif not left and not right:return Trueif left.val != right.val:return FalseoutSide = self.compare(left.left, right.right)inSide = self.compare(left.right, right.left)return outSide and inSide

104.二叉树的最大深度

104. 二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/1.迭代：可以用层序遍历直接做，在每次遍历之前计数加一即可

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 maxDepth(self, root: Optional[TreeNode]) -> int:res = 0if not root:return resfrom collections import dequequeue = deque()queue.append(root)while queue:res += 1length = len(queue)for i in range(length):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return resclass Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:def traver(root):if not root:return 0left = traver(root.left)right = traver(root.right)res = 1 + max(left, right)return resreturn traver(root)

111.二叉树的最小深度

111. 二叉树的最小深度https://leetcode.cn/problems/minimum-depth-of-binary-tree/1.这里层序直接使用上一题的代码，然后在推出节点时，加一个判断，当该节点时叶子节点，直接返回即可。

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 minDepth(self, root: Optional[TreeNode]) -> int:res = 0if not root:return resfrom collections import dequequeue = deque()queue.append(root)while queue:res += 1length = len(queue)for i in range(length):node = queue.popleft()if not node.left and not node.right:return resif node.left:queue.append(node.left)if node.right:queue.append(node.right)return resclass Solution:def minDepth(self, root: Optional[TreeNode]) -> int:def getres(root):if not root:return 0dleft = getres(root.left)dright = getres(root.right)if not root.left and root.right:return 1 + drightif root.left and not root.right:return 1 + dleftres = 1 + min(dleft, dright)return resreturn getres(root)

226. 翻转二叉树

101. 对称二叉树

104.二叉树的最大深度

111.二叉树的最小深度

相关文章：