形状同构代码在特定值上失败

Question

我编写了一个代码来检查2棵树是否同构：

n = int(input())
parent1 = [int(item) for item in input().split()]
parent2 = [int(item) for item in input().split()]


#Structure to store information about nodes
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def add_child(self, node):
        if not self.left:
            self.left = node
        elif not self.right:
            self.right = node

    def __repr__(self):
        return 'TreeNode({self.data!r}, {self.left!r}, {self.right!r})'.format(self=self)



 # Function which converts trees from parent array representation into the usual one.
def construct_tree(parents: list):

    # Put Nodes with corresponding values into the list
    constructed = [TreeNode(i) for i in range(len(parents))]

    root = None
    for i, parent in enumerate(parents):

        # If parent's index = -1, it's the root of the tree
        if parent == -1:
            root = constructed[i]
        else:
            # Tie up current node to corresponding parent
            constructed[parent].add_child(constructed[i])

    return root

def are_isomorphic(T1, T2):
    # Both roots are empty, trees are isomorphic by default

    if len(parent1) != len(parent2):
        return False

    if T1 is None and T2 is None:
        return True
    #if T1.data != T2.data Gives the wrong answer

    # If one of the trees is empty, and the other - isn't, do not bother to check further.
    if T1 is None or T2 is None:
        return False

    # There are two possible cases for n1 and n2 to be isomorphic
    # 1: The subtrees rooted at these nodes haven't been swapped
    # 2: The subtrees rooted at these nodes have been swapped
    return (are_isomorphic(T1.left, T2.left) and are_isomorphic(T1.right, T2.right) or
            are_isomorphic(T1.left, T2.right) and are_isomorphic(T1.right, T2.left))

它对每一棵树都给出了正确的答案，但以下几种除外：

TreeNode(0，TreeNode(1，TreeNode(3，None，None)，TreeNode(4，None，None))，TreeNode(2，None，None)) TreeNode(0，TreeNode(1，TreeNode(3，None，None)，TreeNode(2，TreeNode(4，None，None)

它们不是同构的，但我的代码决定了它们是同构的。

我绘制了这些树，并认为这种情况包含在递归过程中。我试过这个：

if are_isomorphic(T1.left, T2.left) is False:
    return "No"

if are_isomorphic(T1.left, T2.right) is False:
    return "No"

if are_isomorphic(T1.right, T2.left) is False:
    return "No"

if are_isomorphic(T1.right, T2.right) is False:
    return "No"

else:
    return "Yes"

这是：

    if (are_isomorphic(T1.left, T2.left) and are_isomorphic(T1.right, T2.right) is False):
        return "No"

    elif (are_isomorphic(T1.left, T2.right and are_isomorphic(T1.right, T2.left) ) is False):
        return "No"

    else:
        return "Yes"

有人能解释一下我错过了什么吗？

Answer 1

这并不是一个真正的答案，但没有办法在评论中发布代码。正如我所说的，在我看来，您的代码在给出的示例中产生了正确的结果。

#Structure to store information about nodes
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def add_child(self, node):
        if not self.left:
            self.left = node
        elif not self.right:
            self.right = node

def are_isomorphic(T1, T2):
    # Both roots are empty, trees are isomorphic by default

    #if len(parent1) != len(parent2):
        #return False

    if T1 is None and T2 is None:
        return True
    #if T1.data != T2.data Gives the wrong answer

    # If one of the trees is empty, and the other - isn't, do not bother to check further.
    if T1 is None or T2 is None:
        return False

    # There are two possible cases for n1 and n2 to be isomorphic
    # 1: The subtrees rooted at these nodes haven't been swapped
    # 2: The subtrees rooted at these nodes have been swapped
    return (are_isomorphic(T1.left, T2.left) and are_isomorphic(T1.right, T2.right) or
            are_isomorphic(T1.left, T2.right) and are_isomorphic(T1.right, T2.left))

T1=TreeNode(0, TreeNode(1, TreeNode(3, None, None), TreeNode(4, None, None)), TreeNode(2, None, None))

T2=TreeNode(0, TreeNode(1, TreeNode(3, None, None), None), TreeNode(2, TreeNode(4, None, None), None))

print(are_isomorphic(T1, T2))

以上打印False。如果有问题，一定是在你构建树的过程中。