Более общее свойства дерева поиска?

Question

[ChastIOtvaga]

Данная задача полностью аналогична предыдущей, но проверять те-
перь нужно более общее свойство. Дереву разрешается содержать
равные ключи, но они всегда должны находиться в правом поддереве.
Формально, двоичное дерево называется деревом поиска, если для
любой вершины её ключ больше всех ключей из её левого поддерева
и не меньше всех ключей из правого поддерева.
Ограничения. 0 ≤ n ≤ 105; −231 ≤ keyi ≤ 231 −1 (таким образом, в ка-
честве ключей допустимы минимальное и максимальное зна-
чение 32-битного целого типа, будьте осторожны с переполне-
нием); −1 ≤ lefti, righti ≤ n − 1. Гарантируется, что вход зада-
ёт корректное двоичное дерево: в частности, если lefti 6 = −1 и
righti 6 = −1, то lefti 6 = righti; никакая вершина не является сыном
двух вершин; каждая вершина является потомком корня.
Вот код:

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

struct Node {
  int key;
  int left;
  int right;
};

bool is_bst(const vector<Node>& tree, int i, long long min_key, long long max_key, int& last_key) {
  if (i == -1) {
    return true;
  }
  if (tree[i].key < min_key || tree[i].key >= max_key) {
    return false;
  }
  if (!is_bst(tree, tree[i].left, min_key, tree[i].key, last_key)) {
    return false;
  }
  if (last_key != -1 && tree[i].key < last_key) {
    return false;
  }
  last_key = tree[i].key;
  return is_bst(tree, tree[i].right, tree[i].key, max_key, last_key);
}

bool IsBinarySearchTree(const vector<Node>& tree) {
  if (tree.empty()) {
    return true;
  }
  int last_key = -1;
  int i = 0;
  while (tree[i].left != -1) {
    i = tree[i].left;
  }
  if (tree[i].key == numeric_limits<int>::min()) {
    return false;
  }
  return is_bst(tree, 0, numeric_limits<long long>::min(), numeric_limits<long long>::max(), last_key);
}

int main() {
  int n;
  cin >> n;
  vector<Node> tree(n);
  for (int i = 0; i < n; ++i) {
    cin >> tree[i].key >> tree[i].left >> tree[i].right;
  }
  if (IsBinarySearchTree(tree)) {
    cout << "CORRECT" << endl;
  } else {
    cout << "INCORRECT" << endl;
  }
  return 0;
}

прошлую задачу я решил по такому коду :

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

struct Node {
  int key;
  int left;
  int right;
};

bool is_bst(const vector<Node>& tree, int i, long long min_key, long long max_key) {
  if (i == -1) {
    return true;
  }
  if (tree[i].key < min_key || tree[i].key >= max_key) {
    return false;
  }
  return is_bst(tree, tree[i].left, min_key, tree[i].key) &&
         is_bst(tree, tree[i].right, tree[i].key, max_key);
}

bool IsBinarySearchTree(const vector<Node>& tree) {
  if (tree.empty()) {
    return true;
  }
  return is_bst(tree, 0, numeric_limits<long long>::min(), numeric_limits<long long>::max());
}

int main() {
  int n;
  cin >> n;
  vector<Node> tree(n);
  for (int i = 0; i < n; ++i) {
    cin >> tree[i].key >> tree[i].left >> tree[i].right;
  }
  if (IsBinarySearchTree(tree)) {
    cout << "CORRECT" << endl;
  } else {
    cout << "INCORRECT" << endl;
  }
  return 0;
}

Исходя из прошлого кода я поменял bst но всё равно не проходит 20 тест хотя по условиям я проверял тесты которые даны ниже:
Пример.
Вход:
3
2 1 2
1 -1 -1
3 -1 -1
Выход:
CORRECT
Пример.
Вход:
3
1 1 2
2 -1 -1
3 -1 -1
Выход:
INCORRECT
Пример.
Вход:
3
2 1 2
1 -1 -1
2 -1 -1
Выход:
CORRECT
Пример.
Вход:
1
2147483647 -1 -1
Выход:
CORRECT
Пример.
Вход:
5
1 -1 1
2 -1 2
3 -1 3
4 -1 4
5 -1 -1
Выход:
CORRECT
Пример.
Вход:
7
4 1 2
2 3 4
6 5 6
1 -1 -1
3 -1 -1
5 -1 -1
7 -1 -1
Выход:
CORRECT
Больше примеров тестов у меня нету прошу помогите понять в чём дело ибо Wataru пишет но я не могу понять по его объяснению уже какой раз.
ошибка Failed test #20 of 88. Wrong answer

Comments

[ChastIOtvaga]

думал что поможет

bool is_bst(const vector<Node>& tree, int i, long long min_key, long long max_key) {
  if (i == -1) {
    return true;
  }
  if (tree[i].key < min_key || tree[i].key >= max_key) {
    return false;
  }
  if (!is_bst(tree, tree[i].left, min_key, tree[i].key)) {
    return false;
  }
  if (tree[i].key == min_key) {
    int right = tree[i].right;
    while (tree[right].left != -1) {
      right = tree[right].left;
    }
    if (tree[right].key <= tree[i].key) {
      return false;
    }
  }
  return is_bst(tree, tree[i].right, tree[i].key, max_key);
}

bool IsBinarySearchTree(const vector<Node>& tree) {
  if (tree.empty()) {
    return true;
  }
  return is_bst(tree, 0, numeric_limits<long long>::min(), numeric_limits<long long>::max());
}

но нет это не помогло

[ChastIOtvaga]

решил переписав is_bst спасибо за помощь Хаха)

Answer 1

[Wataru]

Что за last_key? Почему дерево считается неправильным, если самая левая вершина равна numeric_limits<int>::min()

Эта задача, в отличии от предыдущих двух ваших вопросов - простая. Тут не надо писать балансированное дерево поиска, а надо тупо проверить, что заданное дерево хорошее.

Отличие от прошлой задачи, упомянутой в вопросе - только в том, что теперь ограничения в каждом поддереве не L < key < R, а L <= key < R. Т.е. отличие от кода в конце вопроса, по идее, должно состоять только в одном знаке <= вместо <

Есть, правда, дополнительная проблема, что числа могут быть очень большие и, например, надо было бы в самом начале передавать numeric_limits<int>::max()+1 в качестве правой границы. Но тут можно решить эту проблему просто заменив тип параметров max_key, min_key на long long. Или изменить их смысл на "ключи в этом поддереве могут быть с L по R включительно". Тогда при переходе к левому сыну надо бы передавать tree[i].key-1 в качестве max_key. Но тогда надо аккуратно и не переполниться при numeric_limits<int>::min(). Но тут тогда нужна дополнительная проверка - любая вершина со значением numeric_limits<int>::min() не должна иметь левых детей.