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