【Python】【二叉树】判断两个二叉树是否相同
程序员文章站
2022-05-16 10:09:55
...
题目描述
相同二叉树的定义:给定两个二叉树,如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
编写一个函数来判断两个二叉树是否相同,相同返回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