Вам дан прохождение P по порядку двоичного дерева поиска по n элементам 1,2,…, n

Question

Вам дан обход по порядку P, бинарного дерева поиска по n элементам 1,2,…, n. Вы должны определить уникальное двоичное дерево поиска, которое имеет P в качестве обхода после заказа. Какова временная сложность наиболее эффективного алгоритма для этого?

A. Θ (logn)

B. Θ (н)

C. Θ (nlogn)

D. Ничего из вышеперечисленного, так как дерево не может быть однозначно определено

Мое понимание:

Исходя из заданного обхода по порядку, мы можем вычислить обход по порядку за время lg (n). так как теперь мы вычислили обход по порядку, мы можем разделить элементы на две части, так как root элемент будет нашим элементом поворота.

Я не знаю, правильно ли я понимаю или нет, вы можете помочь мне визуализировать концепцию.

Answer 1

Должно быть Θ(nlogn). Вам нужно будет пройти как минимум через n узлов, а затем построить двоичное дерево.

Пример из прохождения преодера может быть следующим: Вы можете применить аналогичные логи c для заказа. Использует рекурсию.

Logi c - так как при итерации слева направо мы сначала получим набор элементов, которые меньше первого узла. Эти узлы будут go слева от узла. А остальное будет на правой стороне.

Например:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Код Java для этого:

public TreeNode bstFromPreorder(int[] preorder) {
    if(preorder == null) { return null; }

    if(preorder.length == 0) { return null; }

    TreeNode root = new TreeNode(preorder[0]);

    if(preorder.length == 1) {
        root.left = null;
        root.right = null;
        return root;
    }

    int leftStart = 0;
    if( preorder[1] < preorder[0]) {
        leftStart = 1;
    }

    int rightStart = leftStart+1;

    while(rightStart < preorder.length && preorder[rightStart] < preorder[0]) {
        rightStart++;
    }

    int[] leftPre = new int[0];
    if(leftStart != 0) { 
        leftPre = getSubArray(preorder, leftStart, rightStart);
    }
    int[] rightPre = getSubArray(preorder, rightStart, preorder.length);

    TreeNode leftNode = bstFromPreorder(leftPre);
    TreeNode rightNode = bstFromPreorder(rightPre);

    root.left = leftNode;
    root.right = rightNode;

    return root;  
}


private int[] getSubArray(int[] nums, int leftStart, int rightStart) {
    int[] ans = new int[rightStart - leftStart];

    for(int i = leftStart; i < rightStart; i++) {
        ans[i - leftStart] = nums[i];
    }
    return ans; 
}