Два способа нахождения симметричных деревьев через рекурсию

Question

Сумма кода leet: для двоичного дерева проверьте, является ли оно зеркалом самого себя (т. Е. Симметричным относительно его центра).

Например, это двоичное дерево [1,2,2,3,4,4,3] симметрично:

      1
     / \
    2   2
   / \ / \
  3  4 4  3

Но следующее [1,2,2, ноль, 3, ноль, 3] не является:

    1
   / \
  2   2
   \   \
   3    3

Правильное решениеэто: -

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        else:
            return self.Tsolution(root.left, root.right)

    def Tsolution(self, root1, root2):
        if (root1 == None and root2 == None):
            return True
        if root1 == None or root2 == None:
            return False
        else:
            return (root1.val == root2.val and self.Tsolution(root1.left, root2.right) and
            self.Tsolution(root1.right, root2.left))

Мой вопрос, почему этот код неправильный? Он также выполняет проверку val, но в отдельном условии if.

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        else:
            return self.Tsolution(root.left, root.right)

    def Tsolution(self, root1, root2):
        if (root1 == None and root2 == None):
            return True
        if root1 == None or root2 == None:
            return False
        if root1.val == root2.val:
            return True
        else:
            return (self.Tsolution(root1.left, root2.right) and
            self.Tsolution(root1.right, root2.left))

Это дает мне ошибку во втором примере дерева, приведенном выше.

Answer 1

Упс, я получил ответ.

      1
     / \
    2   2
     \   \
     3    3

Когда мы достигаем 2-го уровня дерева, то есть когда root1.val == 2 и root2.val == 2, наша функция возвращает trueсогласно этому условию:

if root1.val == root2.val:
            return True

и не опускается дальше вниз по функции. Следовательно, мы должны включить это условие вместе с рекурсивным вызовом к левому и правому узлам, как это

 return (root1.val == root2.val and self.Tsolution(root1.left, root2.right) and
            self.Tsolution(root1.right, root2.left))