Название «разделяй и властвуй» происходит от военной науки и означает, что ты разделяешь врага на части и завоевываешь части по отдельности.В алгоритмах, однако, часто вы не пытаетесь закончить каждый фрагмент самостоятельно - вместо этого вы хотите получить single ответ.Так что шаблон немного другой.Вот как происходит «разделяй и властвуй»:
- Разделите задачу на части.
- Решите каждую отдельную часть, рекурсивно применяя весь этот процесс к каждой части.
- Объединитерешения в некотором роде, чтобы получить ответ.
Хитрость заключается в том, чтобы придумать умный способ разделить проблему так, чтобы было возможно объединение решений.Вам не нужно беспокоиться о том, как решить каждую меньшую часть, потому что весь алгоритм - это решение!Это немного волшебно, но становится естественным, когда вы становитесь более знакомыми с рекурсией.
Давайте рассмотрим вашу проблему определения высоты BST.Просто предположите, что каким-то образом по волшебству вы можете найти высоту левого поддерева и высоту правого поддерева.Если у вас есть эти два значения, можете ли вы придумать способ объединить их, чтобы найти высоту всего BST?Если вы не сразу видите ответ, подумайте обо всех функциях двух целых чисел, с которыми вы знакомы, чтобы дать вам идеи.
Вам нужен базовый вариант для рекурсии, но кромечто у нас есть полное решение, хотите верьте, хотите нет:
int BST_height(root) {
if(root is a leaf node)
return 1;
else
return mystery_function(BST_height(root.left), BST_height(root.right));
}