Java return boolean true再帰を使用する

Question

値がバイナリ検索ツリーに含まれているかどうかを確認しようとしていますが、再帰を使用してツリーをトラバースしています。問題は関数が真ではなく呼び出しスタックの最後の値としてfalseを返すことです。ここで

は擬似コードです：

public boolean containsValue(Node node, Value v) { 

    if (node.value.equals(v)) { 
    return true; 
    } 
    containsValue(node.left, v); // <- search left tree 
    containsValue(node.right, v); // <- search right tree 

    return false; 
} 

これは常にfalseを返します。二return文がデッドコードであるので、私はこれを行うことはできませんしかし

：

return containsValue(node.left, v); 
return containsValue(node.left, v); 

それでは、どのように私はこの問題を解決するのでしょうか？

Answer 1

ます。これは、現在のノードの値がパラメータ値と比較する方法をチェックします

public boolean containsValue(Node node, Value value){ 
    int result = node.value.compareTo(value); 
    if(result == 0){ 
     return true; 
    }else if(result < 0){ 
     if(node.left != null){ 
      return containsValue(node.left, v); 
     } 
     return false; 
    }else{ 
     if(node.right != null){ 
      return containsValue(node.right, v); 
     } 
     return false; 
    } 
} 

を行きます。パラメータ値が小さい場合は、左の子の結果を返します(<0)、同じ場合はtrueを返します(==0)、値渡しが大きい場合は、右の子(>0)の結果を返します。これは、値が見つかるまで、または検索が必要な子がnullになるまで続きます。

それはすべての変数をチェックして、Oの平均効率（）N（ログ）を有していないので、この方法は、完全にバイナリ検索ツリーを利用だけのすべてのノードを通して見ることの平均効率を有するのに対しO（n）は非常に最悪です。

追記： その値を持つノードを取得する方法は、基本的に、あなただけのNode

例でnullとbooleanでnodeとtrue、falseを置き換えると同じである：一部の人々が愛する

public Node getNode(Node node, Value value){ 
    int result = node.value.compareTo(value); 
    if(result == 0){ 
     return node; 
    }else if(result < 0){ 
     if(node.left != null){ 
      return containsValue(node.left, v); 
     } 
     return null; 
    }else{ 
     if(node.right != null){ 
      return containsValue(node.right, v); 
     } 
     return null; 
    } 
} 

Answer 2

これはすぐに問題を解決しますが、左または右を見ることを決断しないので、バイナリツリーを検索するための正確で効率的な方法ではありません。その正解はhereです。

---

あなたは左のノードがそれを含んでいるか（||）右のノードがそれを含んでいる場合にtrueを返すようにしたいです。

return containsValue(node.left, v) || containsValue(node.right, v); 

また、左にそれが含まれていれば、短絡して右には見えないことに注意してください。

あなたも、全体のことを行うことができます。

return node.value.equals(v) || 
     containsValue(node.left, v) || 
     containsValue(node.right, v); 

Answer 3

あなたはどちらかの分岐がtrueを返したかどうかを確認し、falseを返すようにしようとする前にそれに沿って渡すことができます。そこ

public boolean containsValue(Node node, Value v) { 

    if (node.value.equals(v)) { 
     return true; 
    } else if (containsValue(node.left, v)) { 
     return true; 
    } else if (containsValue(node.right, v)) { 
     return true; 
    } 

    return false; 
} 

Answer 4

ワンライナー：

public boolean containsValue(Node node, Value v) { 
    return node.value.equals(v) || containsValue(node.left, v) || containsValue(node.right, v); 
} 

Answer 5

public boolean containsValue(Node node, Value v) { 

    if (node.value.equals(v)) { 
    return true; 
    } 
    else if(containsValue(node.left, v)) 
    return true; // <- search left tree 

    else if(containsValue(node.right, v)) // <- search right tree 
    return true; 

    return false; 
} 

現在のところ、関数もtrueを返しますが、検索値と一致するノードに対してのみ、他のすべてのノードに対してはfalseを返します。したがって、コールスタック内で後方に/または上に移動しながら、最終的には最終的な答えとしてfalseを返します。ツリー内の1つのノードの場合にのみ正しくなり、検索値と一致します。