algorithm - 从 PreOrder 构建二叉搜索树

Question

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;
}

Answer 1

有多个二叉树对应任意一个前序遍历。例如，考虑前序遍历 [2,1,3]。这是所有这些树的先序遍历:

  2         2     2          2      2
1   3     1         1      1          1
        3         3          3          3

如果您想唯一地描述一棵二叉树，您需要的不仅仅是前序遍历。

修改问题后添加:其中，只有第一个是有效的二叉搜索树。我不确定给定的前序遍历是否有多个 BST。

如果列表中有重复项，那么对于任何给定的前序遍历都可以有多个树。