0

n2が のサブツリーであるかどうかを確認するために、この関数を作成しましn1た。再帰を使用していますが、2 つのツリーを使用してテストしたところ、間違った答えが返されました (期待されtrueた が、実際には が返されましたfalse)。

私はしばらく苦労しましたが、何が悪いのかまだ言えません。

private Boolean isSubTree(node n1, node n2){
    if(n1 == null)
        return false;
    if(n2 == null)
        return true;
    if(n1.data == n2.data){
        return isSubTree(n1.left,n2.left) && isSubTree(n2.right,n2.right);
    }
    else
        return isSubTree(n1.left, n2) || isSubTree(n1.right, n2);
}
4

4 に答える 4

0

私はnabauに同意します...ノードに親のデータがある場合、天気n2とn1のルートノードをチェックする方が良いです

それ以外の場合は、n1のすべてのノードのノードでn2のルートを確認できます

Javaでは、2つのオブジェクトが同じかどうかを比較できます
。n1のすべてのノードがn2のルートに等しい 場合、ノードが等しい場合は同じです。

于 2013-01-13T18:14:25.513 に答える
0

あなたのエッジケースは正しくありません。特に、 と の両方n1がn2null の場合、一致するサブツリーとしてカウントされますが、1 つだけが null の場合、それは不一致としてカウントされます。

于 2013-01-12T23:28:28.233 に答える
0

n2 の親を調べて n1 かどうかを確認する方が簡単だと思います。そうでない場合は、それが見つかるまでずっと続けます。その場合、true を返します。別の方法は、ルートまでのすべての親が n1 ではないというものです。その場合、false を返します。つまり、n1 のすべての可能な子とその子などをチェックして n2 に到達するのではなく、上に向かって作業します。

于 2013-01-12T23:57:55.090 に答える
0

考慮すべき 2 つのケースがあります。

  1. サブツリーが元のツリーのノードの 1 つでなければならない場合は、ツリーをスキャンして、一致するサブツリー ノードを見つけることができます。
  2. サブツリーに等しい値のみが必要な場合は、再帰的なツリー等価関数を記述し、それを 2 番目の再帰関数で元のツリーのすべての葉に適用する必要があります。
于 2013-01-12T23:59:26.937 に答える