爲了遍歷遞歸循環

Question

我搜索了一段時間SOF和閱讀類似的帖子。我沒有發現任何這些答案令人滿意。我遇到的問題是我想遍歷樹，直到「根節點」和目標節點相同。如果'root'==目標，我想返回true否則爲false。

這是我

private boolean modifiedInorderTraversal(Node newRoot, Node target){  
     if(newRoot.leftPointer != null){ 
      modifiedInorderTraversal(newRoot.leftPointer, target); 
     } 

     if(newRoot == target){ 
      System.out.println("newRoot == target"); 
      return true; 
      //return false; 
     } 

     if(newRoot.rightPointer != null){ 
      modifiedInorderTraversal(newRoot.rightPointer, target); 
     } 

     System.out.println("before false return"); 
    //return true; 
     return false; 
    } 

你會發現註釋掉是返回FALSE，返回true。如果我交換回報，我可以讓程序正常運行所有測試用例。但是，我個人不喜歡這個解決方案。我添加了打印語句來跟蹤哪些問題，並將Netbeans用作我的調試器。當我運行代碼時，它確實顯示它正在輸入

if(newRoot == target){ 
    System.out.println("newRoot == target"); 
    return true; 
    //return false; 
} 

我知道這是因爲我的行被打印出來。現在看來，儘管返回語句爲true，我的遞歸仍然繼續，導致虛假返回。我試過使用全局變量來阻止遞歸無濟於事。 該嘗試的示例

private breakRecursion = false; 

private boolean example(Node newRoot, Node target){ 
    if(!breakRecursion){ 
     if(blah blah){recurse} 
     if(newRoot == target){breakRecursion = true, return true} 
     if(blah blah){recurse} 
     return false; 
    } 
} 

任何想法？我讀過一個可以使用例外的循環，但我認爲這也很麻煩。
***********************更新********************* 我找到了這工作的方式我期望它

private boolean found = false; 
    private boolean modifiedInorderTraversal(Node newRoot, Node target){  
     if(newRoot.leftPointer != null){ 
      modifiedInorderTraversal(newRoot.leftPointer, target); 
     } 

     if(newRoot == target){ 
      found = true; 
     } 

     if(newRoot.rightPointer != null){ 
      modifiedInorderTraversal(newRoot.rightPointer, target); 
     } 

     return found; 
    } 

我對這個解決方案的唯一問題是，運行時是O（n）。最壞的情況應該是O（n），但是這種解決方案不會提前中斷並遍歷所有節點，無論目標是在哪找到的。

Answer 1

您的問題是，當您從遞歸堆棧中的一個級別返回時指示您找到目標，則忘記在較高級別使用此信息來停止搜索。試試這個（取出打印語句在你的課程的最終產品）：

private static boolean modifiedInorderTraversal(Node newRoot, Node target){  
    boolean foundIt = false; 

    if(newRoot.leftPointer != null){ 
     foundIt = modifiedInorderTraversal(newRoot.leftPointer, target); 
     if(foundIt){ 
      System.out.println("Target found in left subtree"); 
      return true; 
     } 
    } 

    System.out.println("searching: "+newRoot.value); 
    if(newRoot == target){ 
     System.out.println("Target found at current node!"); 
     return true; //the target is this node! 
    } 

    if(newRoot.rightPointer != null){ 
     foundIt = modifiedInorderTraversal(newRoot.rightPointer, target); 
     if(foundIt){ 
      System.out.println("Target found in right subtree!"); 
      return true; 
     } 
    } 

    System.out.println("Not found below root "+newRoot.value); 
    return false; //the target is in neither subtree, and is not the root :-(
} 

//My tree: 
//  a 
// / \ 
// b c 
// /\ /\ 
// d e f g 
public static void main(String[] arg){ 
    Node d = new Node(null,null,"d"); 
    Node e = new Node(null,null,"e"); 
    Node f = new Node(null,null,"f"); 
    Node g = new Node(null,null,"g"); 

    Node b = new Node(d,e,"b"); 
    Node c = new Node(f,g,"c"); 

    Node a = new Node(b,c,"a"); 

    System.out.println("Searching for f"); 
    if(modifiedInorderTraversal(a, f)){ 
     System.out.println("Success!"); 
    } 

    System.out.println("---------------------------------"); 

    System.out.println("Searching for q"); 
    Node q = new Node(null,null,"q"); 
    if(modifiedInorderTraversal(a, q)){ 
     System.out.println("Shouldn't make it here..."); 
    } else{ 
     System.out.println("Didn't find q, as we shouldn't"); 
    } 
} 

private static class Node { 
    public Node(Node left, Node right, String value){ 
     leftPointer = left; 
     rightPointer = right; 
     this.value = value; 
    } 
    Node leftPointer; 
    Node rightPointer; 
    String value; 
} 

這將停止搜索，如果該值已經在左子樹中發現，在目前的節點，或右子樹。如果目標沒有在任何一箇中找到，那麼我們放棄。運行以上給出：

Searching for f 
searching: d 
Not found below root d 
searching: b 
searching: e 
Not found below root e 
Not found below root b 
searching: a 
searching: f 
Target found at current node! 
Target found in left subtree 
Target found in right subtree! 
Success! 
--------------------------------- 
Searching for q 
searching: d 
Not found below root d 
searching: b 
searching: e 
Not found below root e 
Not found below root b 
searching: a 
searching: f 
Not found below root f 
searching: c 
searching: g 
Not found below root g 
Not found below root c 
Not found below root a 
Didn't find q, as we shouldn't