【2025-03-02】基础算法：二叉树 相同 对称 平衡 右视图

📝前言说明：
●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频
●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。
●文章中的理解仅为个人理解。
●文章中的截图来源于B站博主灵茶山，如有侵权请告知。

🎬个人简介：努力学习ing
📋本专栏：python刷题专栏
📋其他专栏：C语言入门基础，python入门基础，Linux操作系统基础
🎀CSDN主页 愚润泽

一，视频题目

100. 相同的树

# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:# 问题可以分解成：1，判断根节点是否相同；2，再对左右子树进行比较# 结束条件：当节点为空（这个时候也需要比较）if p is None or q is None:return p is q # p is None and q is None 的简写return q.val == p.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

101. 对称二叉树

# 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:# 把树分成两棵树，即判断：# 1, 根节点是否相同 2, 左边左子树是否等于右边右子树 3, 左边右子树是否等于右边左子树# 结束：节点为空def isSym(left, right):if left is None or right is None:return left is rightreturn left.val == right.val and isSym(left.left, right.right) and isSym(left.right, right.left)return isSym(root.left, root.right)

110. 平衡二叉树

# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:# 判断是否为平衡树需要利用左右子树的高度差# 不断递归遍历子树，寻找到不是平衡树时，剪枝，将结果一直返回到最顶层# 否则，若不是非平衡就是平衡def get_height(root):# 后续遍历 + 将结果往上传# 添加剪枝操作，当发现非平衡返回 -1 然后往上传（因为深度>=0，所以用-1）if root is None: return 0l_height = get_height(root.left)if l_height == -1: return -1r_height = get_height(root.right)if r_height == -1: return -1return max(l_height, r_height) + 1 if abs(l_height - r_height) <= 1 else -1return get_height(root) != -1

199. 二叉树的右视图

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:# 从上到下，先找右子树，再找左子树# 如果深度是首次遇到，就添加ans = []def dfs(node, depth):# 利用depth记录深度if node is None:returnif depth == len(ans):ans.append(node.val)dfs(node.right, depth + 1)dfs(node.left, depth + 1)dfs(root, 0)return ans

二，课后作业

965. 单值二叉树

# 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 isUnivalTree(self, root: Optional[TreeNode]) -> bool:val = root.valdef dfs(node):if node is None: return Trueif node.val != val: return Falsereturn dfs(node.left) and dfs(node.right)return dfs(root)

951. 翻转等价二叉树

# 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 flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:# 有限次的左右交换，即：子树相同或者子树对称if root1 is None or root2 is None: return root1 is root2if root1.val != root2.val: return Falsereturn (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \(self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))

226. 翻转二叉树

# 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 root is None:returnleft = self.invertTree(root.left) # 翻转左子树right = self.invertTree(root.right)root.right = left # 将翻转好的 left 交换到右孩子的位置root.left = rightreturn root  # root 已经是翻转好的

617. 合并二叉树

# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:# 将第二棵合并到第一棵上if root2 is None:return root1if root1 is None:return root2# 中间这一段可以合并写到 TreeNode 中，即：# return TreeNode(root1.val + root2.val,# self.mergeTrees(root1.left, root2.left),  # self.mergeTrees(root1.right, root2.right))root1.val = root1.val + root2.valL = self.mergeTrees(root1.left, root2.left)R = self.mergeTrees(root1.right, root2.right)root1.right = Rroot1.left = Lreturn root1

2331. 计算布尔二叉树的值

# 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 evaluateTree(self, root: Optional[TreeNode]) -> bool:if root.right is None and root.left is None:return True if root.val == 1 else Falseif root.val == 3:return self.evaluateTree(root.left) and self.evaluateTree(root.right)else:return self.evaluateTree(root.left) or self.evaluateTree(root.right)

508. 出现次数最多的子树元素和

# 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 findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:cnt = Counter()def dfs(node):nonlocal cnt# 求树元素和if node is None:return 0s = node.val + dfs(node.left) + dfs(node.right)cnt[s] += 1return sdfs(root)m =  max(cnt.values())return [key for key, value in cnt.items() if value == m]

1026. 节点与其祖先之间的最大差值

# 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 maxAncestorDiff(self, root: Optional[TreeNode]) -> int:ans = 0def dfs(node, mi, mx):nonlocal ansif node is None: return mx = max(node.val, mx)mi = min(node.val, mi)ans = max(ans, node.val - mi, mx - node.val) dfs(node.left, mi, mx)dfs(node.right, mi, mx)dfs(root, root.val, root.val)return ans

1372. 二叉树中的最长交错路径

# 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 longestZigZag(self, root: Optional[TreeNode]) -> int:# 对于每个节点有两种走法：# 1，继续走交错路径，2，重新开发新的路# 走交错路径时要遵守按不同的方向走，因此要记录上一次所走的方向ans = 0def dfs(node, is_right, length):# is_right 代表上一次走的右边nonlocal ansif node is None: returnans = max(ans, length)if is_right:dfs(node.left, False, length + 1) # 继续走dfs(node.right, True, 1) # 开发新路else:dfs(node.right, True, length + 1)dfs(node.left, False, 1)dfs(root, True, 0)return ans

1080. 根到叶路径上的不足节点

# 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 sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:limit -= root.valif root.left is root.right:return None if limit > 0 else rootif root.left:root.left = self.sufficientSubset(root.left, limit)if root.right:root.right = self.sufficientSubset(root.right, limit)return root if root.left or root.right else None # 判断节点是否要删除

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！