Листоподобные деревья

URL вопроса: https://leetcode.com/problems/leaf-similar-trees/

Вопрос:

Рассмотрим все листья бинарного дерева в порядке слева направо. Значения этих листьев образуют последовательность значений листьев.

введите здесь описание изображения

Например, в приведенном выше дереве последовательность конечных значений равна (6, 7, 4, 9, 8).

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

Вернуть true тогда и только тогда, когда два заданных дерева с головными узлами root1 и root2 подобны листьям.

Пример 1:

введите здесь описание изображения

Вход:

root1 = [3,5,1,6,2,9,8,null,null,7,4], 
root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

Вывод: правда

Пример 2:

Вход:

root1 = [1], 
root2 = [1]

Вывод: правда

Пример 3:

Вход:

root1 = [1], 
root2 = [2]

Вывод: ложь

Пример 4:

Вход:

root1 = [1,2], 
root2 = [2,2]

Вывод: правда

Мой код:

class Solution:
    def leafSimilar(self, root1: TreeNode, root2: TreeNode) -> bool:
        def dfs(node1, res=[]):
            if res == None:
                res=[]
            if node1:
                self.leafSimilar(node1.left, None)                
                self.leafSimilar(node1.right, None)
                if node1.left == None and node1.right == None:
                    res.append(node1.val)
                return (res)  
        return (dfs(root1)) == (dfs(root2))

Пройдено 20 кейсов, но он застрял на 21-м кейсе. Тестовый пример, где это не удалось:

Input: root1 = [1,2,3], root2 = [1,3,2]
Expected Output: false

Мой вывод = Истина

Оказывается, листовые узлы — это [2,3] и [3,2], и поэтому он говорит правду, когда это не так. Я попытался использовать список и установить, как я думал, это сравнит последовательность, но не повезло. Что я делаю?


tree depth-first-search
person Shubham    schedule 25.01.2021    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы не должны вызывать leafSimilar рекурсивно, а dfs. Кроме того, нет необходимости передавать dfs второй аргумент, поскольку идея состоит в том, чтобы позволить одному вызову вернуть список, содержащий листья в поддереве данного узла. Таким образом, он не зависит от других вызовов. Затем объедините списки, полученные от левого и правого дочерних элементов, в один список:

def dfs(node1):
    if not node1:
        return []
    res = dfs(node1.left) + dfs(node1.right)
    if node1.left is None and node1.right is None:
        res.append(node1.val)
    return res

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

return dfs(root1) == dfs(root2)

Небольшое примечание: при сравнении с None обычной практикой является использование is (идентификация) вместо ==.

person trincot    schedule 26.01.2021
comment
Не могли бы вы дать обратную связь? - person trincot; 30.01.2021