从inorder和preorder遍历重构二叉树

Question

我编写了以下代码,用于从inorder和preorder遍历构造树.它看起来对我来说是正确的,但它产生的最终树不具有与它构建的输出相同的顺序输出.任何人都可以帮我找到这个功能的缺陷吗？

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}不可能.

也许这个bug不在这个方法中,而是在你的算法中创建inorder和preorder遍历.或者,可能是,您选择了值in[]并pre[]随机？