形状同构代码上

Question

我写了检查代码的特定值失败两棵树是否同构与否：

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)) 

它给出了正确的答案几乎每一个树对，除了这些：

树节点（0，树节点（1，树节点（3，无，无），树节点（4，无， 无）），树节点（2，无，无））

树节点（0，树节点（1 ，TreeNode（3，None，None），None），TreeNode（2， TreeNode（4，None，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。如果有问题，它必须以您构建树的方式进行。