当前位置:网站首页>二叉树 | 对称二叉树、相同的树、子树相同 | leecode刷题笔记
二叉树 | 对称二叉树、相同的树、子树相同 | leecode刷题笔记
2022-08-10 22:23:00 【Begonia_cat】
跟随carl代码随想录刷题
语言:python
101. 简单
对称二叉树
题目:给你一个二叉树的根节点 root , 检查它是否轴对称。
示例1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例2:
输入:root = [1,2,2,null,3,null,3]
输出:false
题目分析
左右节点为空:对称,return true
左节点为空,右节点不为空:不对称,return false
左节点不为空,右节点为空:不对称,return false
左右节点都不为空:比较节点数值,不相同return false
否则:return true
下一步
- 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
- 比较内测是否对称,传入左节点的右孩子,右节点的左孩子。
- 如果左右都对称就返回true ,有一侧不对称就返回false 。
完整代码如下
递归法
# 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 True
return self.compare(root.left, root.right)
def compare(self, left, right):
# 首先排除节点为空的情况
if left == None and right != None:return False
elif left != None and right == None: return False
elif 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
使用队列
使用队列来对比两个树(根节点的左右子树)是否相互翻转
# 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 True
que = collections.deque()
que.append(root.left)
que.append(root.right)
while que:
# 每次从队列中连续取两个值进行下述判断
leftNode = que.popleft()
rightNode = que.popleft()
if not leftNode and not rightNode: # 左节点为空,右节点为空,则对称
continue
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
que.append(leftNode.left) # 左节点的左孩子
que.append(rightNode.right) # 右节点的右孩子
que.append(leftNode.right) # 左节点的右孩子
que.append(rightNode.left) # 右节点的左孩子
return 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
st = [] # 栈
st.append(root.left)
st.append(root.right)
while st:
leftNode = st.pop()
rightNode = st.pop()
if not leftNode and not rightNode:
continue
if not leftNode or not rightNode or leftNode.val != rightNode.val:
return False
st.append(leftNode.left)
st.append(rightNode.right)
st.append(leftNode.right)
st.append(rightNode.left)
return True
100. 相同的树
题目:给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
完整代码如下
# 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:
if not p and not q: # 都为空
return True
elif not p or not q: # 一个为空,一个不为空
return False
elif p.val != q.val: # 都不为空,但是值不相等
return False
else: # 都不为空,值也相等,那就进行递归
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
572. 另一棵树的子树
题目:给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
……待学
边栏推荐
猜你喜欢
CFdiv2-Beautiful Mirrors-(期望)
How many threads does LabVIEW allocate?
LeetCode Daily 2 Questions 02: Reverse the words in a string (1200 each)
音乐播放器(未完成版本)
高学历毕业生,该学单片机还是plc?
Qualcomm Platform Development Series Explanation (Application) Introduction to QCMAP Application Framework
RecyclerView滑动监听
电力系统潮流计算(牛顿-拉夫逊法、高斯-赛德尔法、快速解耦法)(Matlab代码实现)
Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
uni-app微信小程序——下拉多选框
随机推荐
CFdiv2-Common Number-(奇偶数二分+规律)
电力系统潮流计算(牛顿-拉夫逊法、高斯-赛德尔法、快速解耦法)(Matlab代码实现)
STL-stack
测试4年感觉和1、2年时没什么不同?这和应届生有什么区别?
【Maui正式版】创建可跨平台的Maui程序,以及有关依赖注入、MVVM双向绑定的实现和演示
An article to teach you a quick start and basic explanation of Pytest, be sure to read
“数据引擎”开启前装规模量产新赛道,「智协慧同」崭露头角
阿里云新增三大高性能计算解决方案,助力生命科学行业快速发展
CIKM2022 | Sequence Recommendation Based on Bidirectional Transformers Contrastive Learning
RecyclerView滑动监听
瑞幸咖啡第二季营收33亿:门店达7195家 更换CFO
LeetCode Daily 2 Questions 01: Reverse Strings (both 1200) Method: Double Pointer
What would happen if disconnecting during the process of TCP connection?
DC-8靶场下载及渗透实战详细过程(DC靶场系列)
RK3399 platform development series explanation (kernel-driven peripherals) 6.35, IAM20680 gyroscope introduction
Lambda
【开源教程5】疯壳·开源编队无人机-飞控固件烧写
美味的佳肴
Redis
高数_复习_第5章:多元函数微分学