从inorder和preorder遍历重构二叉树

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

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