Почему этот предварительный обход двоичного дерева не возвращает ничего - PullRequest
Новая
       101

Почему этот предварительный обход двоичного дерева не возвращает ничего

0 голосов
/ 28 мая 2020

Привет, я пытаюсь решить leetcode проблему 1379.

Вот постановка задачи + ссылка:

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

Problem

Вот моя неудачная попытка решения: 

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

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if cloned:
            if cloned.val == target.val:
                return cloned
            self.getTargetCopy(original, cloned.left, target)
            self.getTargetCopy(original, cloned.right, target)

Я не понимаю, почему это не работает.

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

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

Однако это не удается автоматические тесты, он даже не проходит пример 1 (на фото выше) и говорит, что возвращает null.

Что мне не хватает?

EDIT:

Я попытался распечатать свое исходное решение с аргументами при каждом вызове функции: 

__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 7, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 4, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = None, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = None, target = 3 )
__main__.Solution.getTargetCopy ( self = <__main__.Solution object at 0x000002B15CF31358>, original = 7, cloned = 3, target = 3 )
None

Так же можно увидеть, как клонированное дерево проходит от 7 до 4, а затем проверяет 4 левого и правого дочерних элементов, которые оба отсутствуют, затем он проверяет правый дочерний элемент 7 7 и подтверждает, что он такой же, как и цель, в этот момент вызова cloned.val=3, поэтому оператор return должен возвращать узел, значение которого равно 3, что должно быть правильным ответом, но, похоже, не возвращая ничего, что даже не является значением клонированного в то время (что доказано оператором печати, показывающим аргументы), что происходит?

1 Ответ

1 голос
/ 29 мая 2020

Когда условие if не выполняется, вы не return ничего.

Поэтому измените эти две строки: 

self.getTargetCopy(original, cloned.left, target)
self.getTargetCopy(original, cloned.right, target)

To: 

res = self.getTargetCopy(original, cloned.left, target)
if res:
    return res
return self.getTargetCopy(original, cloned.right, target)

Или даже (с помощью короткого замыкания): 

return (self.getTargetCopy(original, cloned.left, target)
     or self.getTargetCopy(original, cloned.right, target))
...