Как построить двоичное дерево из уровня порядка массива?

Question

Я работаю над вопросом кодирования и сейчас немного растерялся.Если мне дан массив, который представляет уровень порядка обхода двоичного дерева.Как мне построить дерево из этого?

Пока здесь мой мыслительный процесс: я знаю, что индекс 0th это root, leftChild = 2*i+1 и rightChild = 2*i+2.

Вот что у меня есть, и я не думаю, что это правильно:

public Tree buildTree(ArrayList<Tree> arr, int i) {
    if (i > list.size() - 1) {
        return null;
    }

    root = list.get(i);
    root.LeftChild = buildTree(arr, 2*i+1);
    root.RightChild = buildTree(arr, 2*i+2);

    return root;
}

мой i начинается с 0, спасибо.

Answer 1

Ваш код будет работать только с полными двоичными деревьями , особым случаем двоичных деревьев.

Вы не можете создать общийбинарное дерево только из уровня обхода порядка.

Вам необходимо два обхода, из которых должен быть обход по порядку .

Следующийкомбинация может однозначно идентифицировать дерево.

• Inorder и Preorder.
• Inorder и Postorder.
• Inorder и Level-order.

Хотя есть возможность построить дерево (с учетом только прохождения порядка уровней), если у вас есть несколько разделителей в данном массиве, как описано в в этом посте .

Answer 2

Ваш код выглядит нормально ... хотя странно, что ваш метод принимает ArrayList<Tree> вместо ArrayList<Node>. Почему ты не считаешь это правильным? Как вы тестируете свой метод? Какие ошибки вы получаете?