Для двоичного дерева глубина каждого узла - это кратчайшее расстояние до корня. Здесь узел является самым глубоким, если он имеет наибольшую возможную глубину среди любых узлов всего дерева. Ясно, что в двоичном дереве может быть несколько таких узлов. Поддерево узла определяется как этот узел плюс набор всех потомков этого узла. Нам нужно найти узел с наибольшей глубиной, чтобы он содержал все самые глубокие узлы в своем поддереве.

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

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

Нам нужно сделать две вещи

  • Найдите самые глубокие узлы
  • Найдите их наименьшего общего предка

Давайте сначала найдем самые глубокие узлы. Если задуматься, самые глубокие узлы могут лежать

  • на левой стороне дерева
  • на правой стороне дерева
  • как с левой, так и с правой стороны дерева

На основании чего будет наш наименьший общий предок.

  • левое поддерево
  • правильное поддерево
  • или сам корень (подумайте об этом ..) - мы хотим охватить все самые глубокие узлы, если они находятся с обеих сторон, есть только один узел, который может иметь все из них - Корень

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

Но этот подход кажется очень знакомым? Да, вы правильно угадали, он знаменит - подход Divide & Conquer.

Для каждого узла попросите левое поддерево получить поддерево с самым глубоким узлом, попросите правое поддерево получить самые глубокие узлы, и сравните глубины возвращенных поддеревом. Тот, у кого максимальная глубина, побеждает. Но что, если будет галстук ?. Что ж, в этом случае очевидно, что корень является победителем.

Типичный узел в двоичном дереве будет выглядеть так

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

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

Надеюсь, статья вам понравилась. Если вы хотите прочитать об этом больше, просьба выразить то же самое в форме аплодисментов.