Сравните, одинаковы ли два дерева или нет?

это вопрос https://leetcode.com/problems/то же-дерево/

Вопрос: Имея корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они или нет. Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.

Я использовал Python для решения этой проблемы Это мой подход. Не могли бы вы сказать, почему он не прошел данный тестовый пример? https://leetcode.com/submissions/detail/661792014/

Мой подход:

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

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        a = m = p
        b = n = q
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        
        while a:
            if a.val != b.val:
                return False
            
            if a.left:
                a = a.left
                if b.left:
                    b = b.left
                else:
                    return False
            else:
                if b.left:
                    return False
                else:
                    break
                
            
        while m:
            if m.val != n.val:
                return False

            if m.right:
                m = m.right
                if n.right:
                    n = n.right
                else:
                    return False
            else:
                if n.right:
                    return False
                else:
                    break

        return True

@JonSG, не могли бы вы проверить еще раз?

Vashesh Jogani 17.03.2022 17:16
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
1
22
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема в том, что в вашем цикле whilem пройдет весь путь вниз через одного и того же дочернего элемента (первый цикл: left, второй цикл right), но когда он достигнет конца, он не вернется назад, а затем просмотрит все противоположные поддеревья, которые он пропустил по пути.

Например, возьмем это дерево:

            4
          /   \
         2     6
        / \   / \
       1   3 5   7

Первый цикл будет проверять левую сторону (т.е. 4, 2 и 1), а второй цикл будет проверять правую сторону (т.е. 4, 6, 7), но нет возможности спускаться по дереву зигзагом. Таким образом, узлы с номерами 3 и 5 никогда не проверяются.

Что вам здесь нужно, так это рекурсия. Решить задачу рекурсивно для левого поддерева и еще раз рекурсивно для правого поддерева. Если любой из них возвращает, что есть разница, остановитесь и верните False. Если оба вызова дают положительный результат, а также текущий узел равен, возвращаем True.

Решение (спойлер):

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: return bool(not p and not q or p and q and p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))

Другие вопросы по теме