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

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

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

10 二叉树 一，视频题目100. 相同的树101. 对称二叉树110. 平衡二叉树199. 二叉树的右视图 二，课后作业965. 单值二叉树951. 翻转等价二叉树226. 翻转二叉树617. 合并二叉树2331. 计算布尔二叉树的值508. 出现次数最多的子树元素和1026. 节点与其祖先之间的最大差值1372. 二叉树中的最长交错路径1080. 根到叶路径上的不足节点

一，视频题目 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 right return 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 0 l_height = get_height(root.left) if l_height == -1: return -1 r_height = get_height(root.right) if r_height == -1: return -1 return max(l_height, r_height) + 1 if abs(l_height - r_height) <= 1 else -1 return 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: return if 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.val def dfs(node): if node is None: return True if node.val != val: return False return 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 root2 if root1.val != root2.val: return False return (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: return left = self.invertTree(root.left) # 翻转左子树 right = self.invertTree(root.right) root.right = left # 将翻转好的 left 交换到右孩子的位置 root.left = right return 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 root1 if 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.val L = self.mergeTrees(root1.left, root2.left) R = self.mergeTrees(root1.right, root2.right) root1.right = R root1.left = L return 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 False if 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 0 s = node.val + dfs(node.left) + dfs(node.right) cnt[s] += 1 return s dfs(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 = 0 def dfs(node, mi, mx): nonlocal ans if 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 = 0 def dfs(node, is_right, length): # is_right 代表上一次走的右边 nonlocal ans if node is None: return ans = 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.val if root.left is root.right: return None if limit > 0 else root if 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 # 判断节点是否要删除

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