编程题实训基于二叉链表的树结构相等的判断python

在Python中，如果你需要判断两个基于二叉链表表示的树是否相等，你可以采用递归的方式来实现。这种相等通常意味着两棵树具有相同的结构和元素值。以下是基本步骤：

1. 定义节点类（TreeNode），包含值、左孩子节点和右孩子节点属性。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. 定义一个辅助函数`is_same_tree()`，它接受两个根节点作为参数，然后递归地比较它们的值和子树：

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    elif p is None or q is None:
        return False

    return p.val == q.val and \
           is_same_tree(p.left, q.left) and \
           is_same_tree(p.right, q.right)

这个函数首先检查两个节点是否都为空，如果都为空则代表它们是同构的。接着，它比较节点的值，如果值不同则返回False。最后，它递归地检查左右子树是否也相等。

相关问题

使用二叉链表作为二叉树的储存结构，设计一个算法来判断两棵树是否相等，并给出完整代码

使用二叉链表存储二叉树是一种常见的数据结构表示方式，因为它允许高效的遍历操作。判断两棵二叉树是否相等，即它们的节点值对应位置相同，左右子树也分别相等。可以采用深度优先搜索（DFS）递归的方式来实现这个算法。这里提供一个Python版本的解决方案：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    if not p and not q:
        return True  # 都为空，认为相等
    if not p or not q:
        return False  # 只有一个为空，认为不相等
    if p.val != q.val:
        return False  # 节点值不相等，认为不相等
    
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

# 示例：
# 树1:      1
#            / \
#           2   3
#          / \   \
#         4   5   6
#
# 树2:      1
#            / \
#           2   3
#          / \
#         4   5
# 这两个树就不相等，因为树2的左子树的右子节点6不存在于树1中。

以二叉链表作为二叉树的存储结构，编写如下算法：判别两颗树是否相等

好的，我知道了。以下是以二叉链表作为二叉树的存储结构，判断两颗树是否相等的算法，代码如下：

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def is_equal(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    if root1.val != root2.val:
        return False
    return is_equal(root1.left, root2.left) and is_equal(root1.right, root2.right)

这个算法的时间复杂度为 O(n)，其中 n 是两颗树中节点的数量之和。算法的思路是递归比较两颗树的左子树和右子树是否相等，如果树的根节点的值也相等，则这两颗树相等。注意我们在比较时要判断节点是否为空，否则可能会出现空指针错误。