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

Имея два массива pre[] и in[] , представляющие прямой и неупорядоченный обход двоичного дерева, задача состоит в том, чтобы проверить, допустимы ли данные обходы для любого двоичного дерева или нет без построения дерева. Если это возможно, то выведите Yes . В противном случае выведите Нет .

Примеры:

Input: pre[] = {1, 2, 4, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}
Output: Yes
Explanation:
Both traversals are valid for the following binary tree:
                    1
                 /    
              2        3
          /         / 
       4      5    6 
                     
                 7      8     

Input: pre[] = {1, 2, 69, 5, 7, 3, 6, 8}, in[] = {4, 2, 5, 7, 1, 6, 8, 3}
Output: No

Подход: Идея состоит в том, чтобы использовать аналогичную технику для построения двоичного дерева из обходов в прямом и прямом порядке, за исключением того, что дерево не строится, а проверяется, является ли текущий неупорядоченный обход этого дерева (поддерева) и текущий индекс предварительного порядка действительным или не в каждом рекурсивном вызове или нет.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)