Постановка проблемы:

Имея два бинарных дерева, напишите функцию, которая проверяет, совпадают ли они или нет.

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

Пример 1:

Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true

Пример 2:

Input:     1         1
          /           \
         2             2
        [1,2],     [1,null,2]
Output: false

Что касается вопроса, это вопрос простой категории, и в простой категории есть много таких вопросов, которые помогают построить основы деревьев и рекурсии, отсюда и эта статья.

Решение:

Дано, что если бы деревья были идентичны только структурно, то наш ответ был бы верным. Теперь, чтобы ответить на этот вопрос, мы рассмотрим примеры, чтобы отметить, что «одинаковое» означает не только одинаковое значение, это означает, что каждый узел в одном дереве должен быть равен соответствующему узлу другого дерева. что означает, что каждый узел в каждом поддереве обоих деревьев должен быть равен, поэтому сама эта реализация дает нам представление о рекуррентном отношении, где мы будем проверять значение родительского узла, если оно равно, тогда мы проверяем левое поддерево обоих. деревья и правое поддерево обоих деревьев, если они равны, то мы возвращаем true.

Алгоритм (САМАЯ ВАЖНАЯ ЧАСТЬ РЕШЕНИЯ!!!):

Итак, давайте разработаем алгоритм решения этого вопроса:

  1. если корни обоих деревьев равны NULL, вернуть true.
  2. если корень любого из деревьев равен NULL, вернуть false, поскольку это никогда не будет «то же самое дерево», как указано в описании.
  3. если ни один из вышеперечисленных базовых случаев не является истинным, для текущих узлов (корней) проверяют, равны ли значения, если они не равны, возвращают false.
  4. если сравнение значений дает положительный результат, то проверяем левое и правое поддеревья, рекурсивно вызывая на них функцию.

Псевдокод (СТРОИТЕЛЬНЫЙ БЛОК!!):

  1. bool sameTree(TreeNode* root1, TreeNode* root2){
  2. если корень 1 равен NULL, а root2 равен NULL, вернуть true;
  3. если либо root1 имеет значение NULL, либо root2 имеет значение NULL, вернуть false;
  4. return root1-›value == root2-›value&&sameTree(root1-›left, root2-›left)&&sameTree(root1-›right, root2-›right)

}

На основе этого алгоритма вы можете разработать решение на выбранном вами языке.

Надеюсь, эта статья помогла!

Пожалуйста, не стесняйтесь обращаться ко мне через комментарии (предложения по улучшению всегда приветствуются!)