212
правок
Изменения
Нет описания правки
'''return''' false;
</code>
===Поиск максимального целого поддерева, являющегося целым деревом поиска===
Под размером дерева будем понимать количество вершин в нем. Тогда, чтобы получить решение модифицируем решение предыдущей задачи. Для каждой вершины так же будем хранить размер поддерева поиска, в котором она является корнем. Тогда получается, что для листьев он равен <tex dpi = 120> 1 </tex>, для всех остальных вершин надо проверить является ли их поддерево деревом поиска. Если да, то размер будет равен сумме размеров поддеревьев сыновей плюс один (т.к. учитываем текущую вершину), иначе <tex dpi = 120> 1 </tex>.
ans = v;
currMaxSize = v.size;
'''return''' true;
'''else'''
v.size = 1;
'''return''' false;
</code>
===Поиск максимального поддерева, являющегося деревом поиска===
В этой задаче нам не требуется найти целое дерево, то есть у любой в таком дереве вершины может не быть одного из поддеревьев. Тогда для решения проверку левого и правого поддеревьев надо сделать отдельно.
====Псевдокод====
<code>
'''boolean''' isSearchTree(Node v):
v.max = v.val;
v.min = v.val;
'''boolean''' flag = false; <font color = "green">// true - дерево является деревом поиска, false - нет - лист</font>
v.size = 1;
'''if''' (v.l == null && v.r == null) <font color = "green">// Если текущая вершина - лист</font>
'''if''' (1 > currMaxSize)
ans = v;
currMaxSize = 1;
'''return''' true;
'''if''' (isSearchTree(v.l) && v.l.max < v.val)
v.min = v.l.min;
v.size += v.l.size;
flag = true;
'''if''' (isSearchTree(v.r) && v.r.min > v.val)
v.max = v.r.max;
v.size += v.r.size;
flag = true;
'''if''' (flag && v.size > currMaxSize)
ans = v;
currMaxSize = v.size;
'''if''' (flag)
'''return''' true;
'''else'''
