проверьте, является ли дерево зеркалом

Question

Здравствуйте, у меня есть код, чтобы проверить, является ли дерево зеркальным деревом . Однако он не проходит все тестовые случаи на leetcode.

Я проверил другие источники в Интернете, но, похоже, не могу выяснить ошибку в моем коде.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True

        if root.left and root.right:
            return self.is_symmetric(root.left,root.right) 

    def is_symmetric(self, left, right):

        if (left == None and right == None):
            return True
        if right is None or left is None:
            return False
        if left.val == right.val:
            return True
        return self.is_symmetric(left.left,right.right) and self.is_symmetric(left.right,right.left) 

Спасибо!

Answer 1

Другой способ проверить, является ли дерево зеркальным деревом, - найти пути к каждому узлу, а затем проверить, что все пути обращены:

class Tree:
  def __init__(self, **kwargs):
    self.__dict__ = {i:kwargs.get(i) for i in ['value', 'left', 'right']}
  @staticmethod
  def is_reversed(a, b):
     return True if not a and not b else all(int(c) == (not int(d)) for c, d in zip(a, b))
  def get_paths(self, path = ''):
    yield [self.value, path]
    yield from getattr(self.right, 'get_paths', lambda _:[])(path+'1')
    yield from getattr(self.left, 'get_paths', lambda _:[])(path+'0')

t = Tree(value=31, left=Tree(value=16, left=Tree(value=7), right=Tree(value=24, right=Tree(value=29), left=Tree(value=19))), right=Tree(value=45))
t1 = Tree(value=31, right=Tree(value=16, right=Tree(value=7), left=Tree(value=24, right=Tree(value=19), left=Tree(value=29))), left=Tree(value=45))
"""
        31     |      31
      /    \   |     /  \
    16      45 |   45   16
   /  \        |        / \
  7   24       |       24  7
     /  \      |      /  \
    19   29    |     29  19

"""
_paths1 = dict(list(t.get_paths()))
_paths2 = dict(list(t1.get_paths()))
print(all(Tree.is_reversed(_paths1[i], _paths2[i]) for i in _paths1))

Вывод:

True

Answer 2

Если условие, проверяющее root.left and root.right, равно False, ваша функция isSymmetric неявно возвращает None. Вместо этого он должен продолжать проверять, является ли один из root.left или root.right не None, в этом случае он должен возвращать False; в противном случае root.left и root.right равны None, и он должен вернуть True. Кроме того, в функции is_symmetric то, что left.val == right.val не означает, что левое поддерево симметрично правому поддереву, поскольку под ними может быть больше дочерних элементов. Он должен просто вернуть False, когда left.val != right.val:

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

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        if root.left and root.right:
            return self.is_symmetric(root.left,root.right)
        if root.left or root.right:
            return False
        return True

    def is_symmetric(self, left, right):

        if left is None and right is None:
            return True
        if right is None or left is None or left.val != right.val:
            return False
        return self.is_symmetric(left.left, right.right) and self.is_symmetric(left.right, right.left)