遞歸地搜索二叉樹

Question

嗨我無法正常工作。當它沿着樹的最左邊向下遞歸時，它似乎跳出堆棧。我似乎無法弄清楚這一點。

public static Node lookup(Node node, int lookupValue) { 

     if (node == null) { 
      return null; 
     } else { 
      if (node.value == lookupValue) { 
       System.out.println("Found"); 
       return node; 
      } else if(node.left != null) { 
       return lookup(node.left, lookupValue); 

      } else if(node.right != null) { 
       return lookup(node.right, lookupValue); 
      } else { 
       return null; 
      } 
     } 
} 

Answer 1

您返回左子樹（如果存在）返回的任何內容，而不檢查正確的子樹。當if塊中有return語句時，不需要很多else分支。更改如下：

public static Node lookup(Node node, int lookupValue) { 
    if (node == null) 
     return null; 
    if (node.value == lookupValue) 
     // System.out.println("Found"); 
     return node; 
    Node rval = lookup(node.left, lookupValue); 
    // only return if found in left sub-tree 
    return (rval != null) ? rval : lookup(node.right, lookupValue); 
} 

Answer 2

你else if是不正確的，你chould檢查左，右everytimes：

if (node == null) return null; 
if (node.value == lookupValue) { 
    System.out.println("Found"); 
    return node; 
} 
Node found = lookup(node.left, lookupValue); 
if(found != null) { 
    return found; 
} 
return lookup(node.right, lookupValue);