跟随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 也可以看做它自身的一棵子树。
题目分析
先明确一下,什么是子树?
如果包含根节点在内,那子树
就是整棵树
,这个概念要理清。也就是说:
下面这个图
不是子树!!!不是子树!!!不是子树!!!
判断是否为子树,分为三种情况:
树1
的根节点 与树2
的根节点 进行相同树函数
判断,如果相同,就返回True
- 既然走到第二步了,就说明两个树的根节点不相同。因此往下判断:如果:
树1
的节点的右节点 与树2
的节点 进行子树函数
判断树1
的节点的左节点 与树2
的节点 进行子树函数
判断树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 isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
if root == None and subRoot == None:
return True
if root == None or subRoot == None:
return False
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) or self.isSameTree(root, subRoot)
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)
本文含有隐藏内容,请 开通VIP 后查看