【Python】【⼆叉树】判断两个⼆叉树是否相同题⽬描述
相同⼆叉树的定义：给定两个⼆叉树，如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。编写⼀个函数来判断两个⼆叉树是否相同，相同返回True否则返回False。
解法⼀：使⽤递归求解
# 树的节点类
class TreeNode:
def__init__(self, x):
self.val = x
self.left =None
self.right =None
def isSameTree(p: TreeNode, q: TreeNode)->bool:
# 两者都为None则返回True
if not p and not q:
return True
# 其中⼀个为None则返回False
if not p or not q:
return False
# 都不为None则⽐较值
if p.val != q.val:
return False
# 对左右⼦树分别进⾏递归⽐较
return isSameTree(p.left, q.left)and isSameTree(p.right, q.right)
解法⼆：迭代+队列
def isSameTree(p: TreeNode, q: TreeNode)->bool:
# 判断树的根节点是否都为空
if not p and not q:
return True
queue =[(p, q)]
while queue:
p_node, q_node = queue.pop(0)
# 其中之⼀为None则返回False
if(p_node and not q_node)or(not p_node and q_node):
return False
二叉树定义# ⽐较节点的值
if p_node.val == q_node.val:
# 左⼦树只要有⼀个不为None，就加⼊队列
if p_node.left or q_node.left:
queue.append((p_node.left, q_node.left))
# 右⼦树只要有⼀个不为None，就加⼊队列
if p_node.right or q_node.right:
queue.append((p_node.right, q_node.right))
else:
return False
return True

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。