День 18: Задача «Поддерево другого дерева»

День 18: Задача «Поддерево другого дерева»

Проблема:

Учитывая два непустых двоичных дерева s и t, проверьте, имеет ли дерево t точно такую ​​же структуру и узел. значения с поддеревом s. Поддерево s - это дерево, состоящее из узла в s и всех потомков этого узла. Дерево s также можно рассматривать как поддерево самого себя.

Пример 1
Данное дерево:

     3
    / \
   4   5
  / \
 1   2

Для данного дерева t:

   4 
  / \
 1   2

Верните true, потому что t имеет ту же структуру и значения узлов с поддеревом s.

Пример 2
Данное дерево:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Для данного дерева t:

   4
  / \
 1   2

Вернуть false.

Мое решение:

def preorder(self, node: TreeNode):
    if node is None:
        return ""
    left = self.preorder(node.left).strip()
    right = self.preorder(node.right).strip()
    return (" " + str(node.val) + " " 
            + ("null" if left == "" else left)  + " "
            + ("null" if right == "" else right) + " "
    )
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
    return self.preorder(t) in self.preorder(s)

Пояснение:

Прежде чем двигаться дальше, давайте попробуем понять, как обходится предзаказ.

Предварительный обход - это один из многих способов обхода дерева.

В обходе предварительного заказа мы,

1. Посетите корень
2. Рекурсивно пройти по левому поддереву
3. Рекурсивно пройти по правому поддереву

Возьмем пример 1,

Для s обход предварительного заказа будет происходить, как показано ниже:

Мы видим, что предварительный заказ на s равен 34125.

Точно так же для t обход предварительного заказа будет таким:

Как мы видим, предварительный заказ на t - 412.

Мы видим, что при предварительном обходе мы обрабатываем 5 только после обработки всего поддерева в 4. Итак, мы знаем, что предварительный порядок поддерева в 4, то есть 412, будет подстрокой предварительного порядка всего дерева.

Следовательно, мы можем заключить, что если у нас есть дерево t, оно будет поддеревом в дереве s, только если предварительный порядок t является подстрокой предварительного порядка s.

Вот как мы проверяем, является ли дерево «поддеревом другого дерева».

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

Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в качестве комментариев вместе со ссылкой на описание проблемы.

Увидимся завтра!

Ваше здоровье!