java - 从中序和先序遍历重建二叉树

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 是在函数外声明的static。

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[] 的值？