Решение задачи №80 от UniLecs

can_be_path_in_bst.rs

//Включить использование паттернов для слайсов.
//На текущий момент (20 марта 2018) эта фича доступна
//только на ночной версии компилятора
#![feature(slice_patterns)]

//Тип элементов в проверяемом массиве
type Elem = i64;

//Проверяет, находятся ли все элементы arr в одном и том же
//отношении порядка (т. е. все больше, все меньше или все равны)
//относительно pivot. Возвращает true, если массив пустой.
fn same_relation(pivot: Elem, arr: &[Elem]) -> bool {
    match *arr {
        [] => true,
        [_single] => true,
        [first, ref rest..] =>  {
            let relation = pivot.cmp(&first);
            rest.iter().all(|x| pivot.cmp(x) == relation)
        },
    }
}

//Проверяет, может ли переданная последовательность элементов
//быть путём от корня к листу в бинарном дереве поиска.
//Возвращает true, если массив пустой.
fn can_be_path_in_bst(arr: &[Elem]) -> bool {
    for i in 0..arr.len() {
        match arr[i..] {
            [] => return true,
            [_single] => return true,
            [first, ref rest..] =>
                //Если последовательность является путём в бинарном
                //дереве поиска, то для каждого элемента последовательности
                //последующие либо все больше, либо все меньше
                if !same_relation(first, rest) { return false },
        }
    }
    true
}

//Альтернативный вариант решения. В отличие от предыдущего,
//имеет сложность O(n), а не O(n^2)
fn can_be_path_in_bst2(arr: &[Elem]) -> bool {
    match *arr {
        [] => true,
        [_single] => true,
        [first, ref rest..] => {
            use std::cmp::Ordering;
            
            //Границы значения элемента
            let (mut lower, mut upper) = (Elem::min_value(), Elem::max_value());
            let mut prev = first;
            
            //Для каждого элемента в последовательности
            for &curr in rest {
                //Если текущий элемент не входит в заданный интервал, то
                //последовательность не может быть путём в бинарном дереве поиска
                if curr < lower || curr > upper {
                    return false;
                }
                
                //Корректируем интервал относительно предыдущего элемента
                match curr.cmp(&prev) {
                    Ordering::Less => upper = prev,
                    Ordering::Equal => (),
                    Ordering::Greater => lower = prev,
                };
                
                prev = curr;
            }            
            true
        },
    }
}

//------------------------------------------------------------

//Тесты
#[test]
fn some_variants() {
    let arr = [8, 3, 6, 4];
    assert_eq!(can_be_path_in_bst(&arr), true);
    assert_eq!(can_be_path_in_bst2(&arr), true);
    
    let arr = [8, 4, 6, 3];
    assert_eq!(can_be_path_in_bst(&arr), false);
    assert_eq!(can_be_path_in_bst2(&arr), false);
    
    let arr = [1, 2, 3, 4, 5];
    assert_eq!(can_be_path_in_bst(&arr), true);
    assert_eq!(can_be_path_in_bst2(&arr), true);
    
    let arr = [5, 1, 2, 3, 4];
    assert_eq!(can_be_path_in_bst(&arr), true);
    assert_eq!(can_be_path_in_bst2(&arr), true);
    
    let arr = [3, 1, 2, 4, 5];
    assert_eq!(can_be_path_in_bst(&arr), false);
    assert_eq!(can_be_path_in_bst2(&arr), false);
}

//Тестирование случая пустого массива
#[test]
fn empty() {
    let arr = [];
    assert_eq!(can_be_path_in_bst(&arr), true);
    assert_eq!(can_be_path_in_bst2(&arr), true);
}

//Тестирование случая масиива, содержащего
//единственный элемент
#[test]
fn single() {
    let arr = [8];
    assert_eq!(can_be_path_in_bst(&arr), true);
    assert_eq!(can_be_path_in_bst2(&arr), true);
}

Playground rev1: https://play.rust-lang.org/?gist=c37da54bef9a4e2627a32591e9cd2705&version=nightly
Playground rev2: https://play.rust-lang.org/?gist=aeaef36e379e58cbf5de4ea81c7512e0&version=nightly