欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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
相关标签: 算法