Является ли данное двоичное дерево действительным BST? - PullRequest
Новая
       28

Является ли данное двоичное дерево действительным BST?

0 голосов
/ 12 июня 2019

Если дерево BST.тогда обход по порядку должен дать нам отсортированный массив.И если массив отсортирован, то данное дерево должно быть BST, тогда почему этот код не выполняется

Заранее спасибо 

void getInorder(vector<int> &inorder, TreeNode* A){

    if(A == NULL)
        return;
    getInorder(inorder,A->left);
    //cout<<A->val<<" ";
    inorder.push_back(A->val);
    getInorder(inorder,A->right);
}

int Solution::isValidBST(TreeNode* A) {
    //If it is a valid BST //Then its inorder Must be a sorted array;
    vector<int> inorder;

    if(A == NULL)
        return 0;

    getInorder(inorder,A);

    // for(int a:inorder)
    //     cout<<a<<" ";

    cout<<endl;
    return is_sorted(inorder.begin(), inorder.end()) == true ? 1 : 0;
}

Выход 1: Это BST, 0: НеBST 

Failing Test Case :

     2
   /   \
  1     2

Его обход InOrder: 1,2,2 (отсортировано) MyCode O / P: 1, ожидаемое O / P: 0

Причина: (Это не BST, Поскольку Right Sub дерево должно иметь значение больше Root, в этом случае оно равно root)

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

1 Ответ

0 голосов
/ 15 июня 2019

Проблема в том, что {1, 2, 2} на самом деле отсортированный список. Следовательно, std::is_sorted возвращает true для такого массива. Вот небольшой пример для экспериментов: 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int main()
{
    std::vector<int> mtmd = {1, 2, 3, 4, 5, 5};
    std::cout << std::is_sorted(mtmd.begin(), mtmd.end()) << std::endl;

}

Вывод true, который должен быть. Лучшее решение - реализовать свой собственный is_sorted.

...