形狀同構代碼上

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。如果有問題，它必須以您構建樹的方式進行。