preorderTransaversal构建二叉搜索树的方法,有什么建议请指教。
Node constructTreeFromPreorder(int[] arr,int start,int end)
{
if(arr==null){
return null;
}else{
if(start>end){
return null;
}
int element=arr[start];
Node node=new Node(element); // create node
if(start==end){
return node;
}
int index=start+1;
for(int i=index;i<=end;i++){
index=i;
if(arr[i]>element){
break;
}
}
node.left=constructTreeFromPreorder(arr, start+1, index-1);
node.right=constructTreeFromPreorder(arr, index, end);
return node;
}
最佳答案
有多个二叉树对应任意一个前序遍历。例如,考虑前序遍历 [2,1,3]
。这是所有这些树的先序遍历:
2 2 2 2 2
1 3 1 1 1 1
3 3 3 3
如果您想唯一地描述一棵二叉树,您需要的不仅仅是前序遍历。
修改问题后添加:其中,只有第一个是有效的二叉搜索树。我不确定给定的前序遍历是否有多个 BST。
如果列表中有重复项,那么对于任何给定的前序遍历都可以有多个树。
关于algorithm - 从 PreOrder 构建二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47315048/