recursion - 从预购重建 BST，逻辑错误

Question

试图围绕如何更正我的代码。我有这个想法，但我在实施过程中陷入困境。

当我单步执行下面的代码时，我可以从预购遍历中重建 BST 的一部分。但在某些时候，我会有这样的函数调用：

recon(preOrd,2,2) 

这导致未分配叶子。我还不知道如何纠正这个问题。

我已经看到有关此主题的其他线程，但想解决我的问题，以便我可以真正了解重建 BST 的概念。

public static Node recon(int[] preOrd,int start,int end){

if (start==end){
        return null;
    }
    Node root = new Node (preOrd[start]);   
    int div=start;
    for (i=start+1;i<=end && preOrd[i]<preOrd[start];i++){ 
        div=i;
    }
Node left= reconstruct(preOrd,start+1,div);
Node right= reconstruct(preOrd,div+1,end);

root.setLeft= left;
root.setRight=right;
    return root;
}

Answer 1

事实证明这很简单。只需要纠正我对更新叶节点的想法..

public static Node recon(int[] preOrd,int start,int end){
    Node root = new Node (preOrd[start]);//declare the new node      
    if (start>end){ //this is illegal, so return null 
            return null;
        }
    if (start==end){
            return root;
        }  
        int div=start;
        for (int i=start+1;i<=end preOrd[i]<preOrd[start];i++){ 
            div=i;
        }
    Node left= reconstruct(preOrd,start+1,div);
    Node right= reconstruct(preOrd,div+1,end);

    root.setLeft= left;
    root.setRight=right;
    return root;
    }