Проверка корректности двоичного дерева

@PABchic · Регистрация: 17.02.2017

Студворк — интернет-сервис помощи студентам

Здравствуйте!
Задача такая,

Свойство двоичного дерева поиска можно сформулировать следующим образом: для каждой
вершины дерева V выполняется следующее условие:
• все ключи вершин из левого поддерева меньше ключа вершины V ;
• все ключи вершин из правого поддерева больше ключа вершины V .
Дано двоичное дерево. Проверьте, выполняется ли для него свойство двоичного дерева поиска.
Формат входного файла
Входной файл содержит описание двоичного дерева. В первой строке файла находится число
N (0 ≤ N ≤ 200000) — число вершин в дереве. В последующих N строках файла находятся описания
вершин дерева. В (i + 1)-ой строке файла (1 ≤ i ≤ N) находится описание i-ой вершины, состоящее
из трех чисел Ki, Li, Ri разделенных пробелами — ключа в i-ой вершине (|Ki| ≤ 10^9), номера левого
ребенка i-ой вершины (i < Li ≤ N или Li = 0, если левого ребенка нет) и номера правого ребенка
i-ой вершины (i < Ri ≤ N или Ri = 0, если правого ребенка нет).
Формат выходного файла
Выведите «YES», если данное на входе дерево является двоичным деревом поиска, и «NO», если
не является.

пример входного файла:
3
5 2 3
6 0 0
4 0 0

пример выходного файла:
NO

пример входного файла:
6
-2 0 2
8 4 3
9 0 0
3 5 6
0 0 0
6 0 0

пример выходного файла:
YES

Я считываю само дерево, далее вызываю функцию, которая начинает от корня дерева и в случае, если с корнем и его детьми все ок, запускается для каждого из детей. Считаю, что корень дерева - первый элемент массива (в условии не сказано, но вроде это так)
на всех моих тестах работало, но в проверяющей системе не проходит тест 8

вот мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <fstream>
struct BinarySearchTree
{
    int value;
    int left;
    int right;
};
bool isBST(BinarySearchTree *, int const &);
int main()
{
    std::ifstream fin("input.txt");
    std::ofstream fout("check.txt");
    int n;
    fin >> n;
    if (n == 0)
    {
        fout << "YES";
        fout.close();
        fin.close();
        return 0;
    }
    BinarySearchTree *tree;
    tree = new BinarySearchTree[n + 1];
    for (int i = 1; i <= n; i++)
        fin >> tree[i].value >> tree[i].left >> tree[i].right;
    if (isBST(tree, 1))
        fout << "YES";
    else
        fout << "NO";
    fin.close();
    fout.close();
    return 0;
}
bool check(BinarySearchTree *tree, int const &j, int const &k, int const &c)
{
    switch (k)
    {
    case 0:
        if (tree[j].value > c)
            return false;
        break;
    case 1:
        if (tree[j].value < c)
            return false;
        break;
    }
    if (tree[j].left != 0 && !check(tree, tree[j].left, k, c))
        return false;
    if (tree[j].right != 0 && !check(tree, tree[j].right, k, c))
        return false;
    return true;
}
bool isBST(BinarySearchTree *tree, int const &j)
{
    if (tree[j].left == 0 && tree[j].right == 0)
        return true;
    if (tree[j].left != 0 && tree[j].value < tree[tree[j].left].value)
        return false;
    if (tree[j].right != 0 && tree[j].value > tree[tree[j].right].value)
        return false;
    if (tree[j].left != 0 && !check(tree, tree[j].left, 0, tree[j].value))
        return false;
    if (tree[j].right != 0 && !check(tree, tree[j].right, 1, tree[j].value))
        return false;
    if (tree[j].left != 0 && isBST(tree, tree[j].left) == false)
        return false;
    if (tree[j].right != 0 && isBST(tree, tree[j].right) == false)
        return false;
    return true;
}

@_Ivana · 24.03.2017, 01:50

Однако, вижу 3 возможных варианта:
- не проходит по времени
- неправильно строится дерево
- неправильно проверяется дерево

Навскидку кот. Конечно при 200000 элементах надо !! по списку заменить на вектор / сет / мап или т.п. со скоростью доступа О(1) / О(log n)

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
 
data BT a = E | N (BT a) a (BT a) deriving (Show, Foldable)
 
task = valid . make. map (map (\x -> read x::Int) . words) . tail . lines
 
make = go 1 where
    go 0 _ = E
    go i s = N (go l s) k (go r s) where [k,l,r] = s !! (i-1)
 
valid E = True
valid (N l k r) = all (<k) l && all (>k) r && valid l && valid r
 
main = getContents >>= print . task

Если есть ссылка на проверяющую систему, можно проверить.

@PABchic · 24.03.2017, 21:35 **[ТС]**

Честно говоря синтаксис совсем непонятен) в принципе проблем с реализацией того или иного алгоритма нет, вопрос в том, что раз система не принимает решение (которое было переписано в различных вариациях схожих по смыслу), то проблема в самом алгоритме)
З.Ы. решение выдает неверный ответ, а по времени все ок) возможно кто-нибудь посоветует какой-нибудь алгоритм, или укажет, чего я не учитываю или не вижу?...

Новые блоги и статьи Все статьи Все блоги /
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .

@PABchic 0 / 0 / 0 Регистрация: 17.02.2017 Сообщений: 3
	24.03.2017, 21:35 [ТС]
	Честно говоря синтаксис совсем непонятен) в принципе проблем с реализацией того или иного алгоритма нет, вопрос в том, что раз система не принимает решение (которое было переписано в различных вариациях схожих по смыслу), то проблема в самом алгоритме) З.Ы. решение выдает неверный ответ, а по времени все ок) возможно кто-нибудь посоветует какой-нибудь алгоритм, или укажет, чего я не учитываю или не вижу?... 0