PreOderからBSTを再構築し、ロジックのエラーです
-
26-12-2019 - |
質問
コードを訂正する方法について私の頭を包むようにしようとしています。私はその考えを持っていますが、私は実装中に立ち往生します。
以下のコードを踏むと、予約注文のトラバーサルから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;
}
. 解決
これはかなり簡単です。リーフノードの更新についての私の考えを修正する必要がありました。
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;
}
. 所属していません StackOverflow