Поиск двоичного дерева рекурсивно

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

Вы возвращаете все возвращаемое из левого поддерева (если оно имеется) без проверки правильного. Большая часть разветвления else не требуется, если в блоке if есть оператор return. Изменить следующим образом:

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