递归地搜索二叉树

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);