Восстановление бинарного дерева по обходам по порядку и по предзаказу

Question

Я написал следующий код для построения дерева по его обходам и обходам. Для меня это выглядит правильно, но итоговое дерево, в результате которого оно получается, не имеет того же вывода, что и его построенное. Может кто-нибудь помочь мне найти недостаток в этой функции?

public btree makeTree(int[] preorder, int[] inorder,  int left,int right)
{
    if(left > right)
        return null;

    if(preIndex >= preorder.length)
        return null;

    btree tree = new btree(preorder[preIndex]);
    preIndex++;

    int i=0;
    for(i=left; i<= right;i++)
    {
        if(inorder[i]==tree.value)
            break;

    }


        tree.left = makeTree(preorder, inorder,left, i-1);
        tree.right = makeTree(preorder, inorder,i+1, right );

    return tree;

}

Примечание: preIndex - это статический объект, объявленный вне функции.

Answer 1

in = {1,3,2,5}; pre = {2,1,5,3};

У меня есть некоторые трудности при построении дерева «вручную». pre показывает, что 2 должен быть корнем, in показывает, что {1,3} является узлами левого поддерева, {5} - правое поддерево:

      2
     / \
    /   \
  {1,3} {5}

Но, зная это, 3 не может быть последним элементом в pre, потому что это явно элемент левого поддерева и , у нас есть правое поддерево. Допустимые обходы для этих деревьев: {2,1,3,5} или {2,3,1,5}. Но {2,1,5,3} невозможно.

Может быть, ошибка не в этом методе, а в вашем алгоритме создания обходов по предзаказу и по предзаказу. Или, может быть, вы выбрали значения для in[] и pre[] случайным образом?