Давайте по аналогии с кодированием напишем рекурсивную функцию раскодирования.

Пусть наша функция должна построить поддерево, в котором для всех вершин выполняется $$$lef < x_i < rig$$$ (другими словами, ключи в нашем поддереве могут лежать только в интервале $$$(lef, rig)$$$). Если очередное рассматриваемое по порядку число не принадлежит интервалу, то наше поддерево пустое, так как первым числом всегда идёт корень. В противном случае запустим расшифровку левого и правого поддерева, изменив границы допустимых ключей.

Расшифровка на языке C++:

[language=C++]
int build_tree(int &uk, int lef, int rig, int n)
{
    if (uk == n + 1) return -1;
    int val = perm[uk];
    if (val <= lef || val >= rig) return -1;

    uk++;
    left_son[val] = build_tree(uk, lef, val, n);
    right_son[val] = build_tree(uk, val, rig, n);
    return val;
}

Заметим, что результат расшифровки всегда — корректное бинарное дерево поиска, так как мы соблюдаем ограничения на ключи в поддеревьях.

Если нам удалось расшифровать весь массив, то найденное дерево и есть ответ. Иначе закодированная запись некорректна.

Итоговая асимптотика — $$$\mathcal{O}(n)$$$.