从中序遍历和前序遍历重构二叉树

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是在函数外声明的静态变量。

- Sid

---

没有。这是一个我正在尝试回答的有趣问题。我想这没有什么害处。 - Sid

输入 = {1,3,2,5}; 前序 = {2,1,5,3};对于这种情况，新树的中序遍历结果为{1,5,2,3}，而前序遍历仍然正常。 - Sid

我有疑问，你需要指定根节点才能从任何遍历方式中唯一重建一棵树，这是正确的吗？因此，如果没有指定根节点，则结果正确的唯一可能性是完全平衡的树，是吗？ - Javaguru

由于我们有先序遍历和中序遍历，因此构建树就足够了。根节点只是先序遍历中的第一个节点。思路是一旦在中序数组中找到节点，我们就可以在这里分割数组，并且左右子树也在中序中，因此我们可以递归地构建树。 - Sid

根节点是前序遍历中的第一个节点。 - Maurice Perry

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[]的值是随机的吗？

- Andreas Dolk

---

糟糕！我想这是正确的。我不能相信我浪费了这么多时间，认为我误解了递归，而事实上我一直是正确的。谢谢。 - Sid