это вопрос 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
Проблема в том, что в вашем цикле while
m
пройдет весь путь вниз через одного и того же дочернего элемента (первый цикл: 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))
@JonSG, не могли бы вы проверить еще раз?