java - 无法停止递归java

Question

我正在尝试使用它的标签搜索节点并在目标节点下添加一个新节点，当我尝试使用递归搜索它时，它总是返回错误的目标或返回 null。谁知道怎么修它？

public TreeNode getNodeReference(String label){

    if(left!=null){
        if(check(left,label)==true)
            return left;
         left.getNodeReference(label);
    }

    if(middle!=null){
        if(check(middle,label)==true)
           return middle;
        middle.getNodeReference(label);
    }
    if(right!=null)
     { if(check(right,label)==true)
          return right;
        right.getNodeReference(label);
    }
    return null;
}


public boolean check(TreeNode tree,String label){

    if(tree.getLabel().equals(label))
        return true;
    else return false;
}

Answer 1

问题是：您没有对内部调用的返回值做任何事情。

举个例子 ：

1. 左不为空
2. 检查返回假
3. 使用标签调用 getNodeReference
4. left 不为空
5. 检查返回真
   （第一次调用返回真，但你什么也抓不到）
6. 中间不为空

7. 检查
   ……

   十、返回空值；
   
   繁荣！

Answer 2

如果你真的跟踪你的代码，你可以很清楚地看到为什么它会返回一个不正确的结果。如果树的第一级的子级都没有与标签匹配（假设左/中/右都是非空的），我在下面标记了代码路径：

public TreeNode getNodeReference(String label){

  if(left!=null){ // 1: left is not null
    if(check(left,label)==true) // 2: no match, proceed to 3
        return left;
    left.getNodeReference(label); // 3: called, but why? no side effect, no return.
  }

  if(middle!=null){ // 4
    if(check(middle,label)==true) // 5
       return middle;
    middle.getNodeReference(label); // 6
  }

  if(right!=null) { // 7
    if(check(right,label)==true) // 8
       return right;
    right.getNodeReference(label); // 9
  }

  return null; // 10: and finally we're here and we return null
}

本质上，您调用 child.getNodeReference(label)，但这就是您所做的一切。你叫它。然后您丢弃返回的值并继续，因此您的搜索实际上永远不会下降到您最初调用 getNodeReference 的节点的第一级之外。

所以对于初学者来说，这个一般模式就是你想要的：

if (child != null) { 
    if (check(child, label))
        return child; // match found
    TreeNode childResult = child.getNodeReference(label);
    if (childResult != null)
        return childResult; // match found deeper in tree; this is what you did not do.
}

也就是说，这是一个较短的实现（请记住，这与您所拥有的并不完全相同，因为您的实现也跳过了检查 getNodeReference 首次调用的实际节点）：

public TreeNode getNodeReference (String label) {

    if (check(this, label))
        return this;

    TreeNode childResult = null; 
    if (left != null)
        childResult = left.getNodeReference(label);
    if (childResult == null && middle != null)
        childResult = middle.getNodeReference(label);
    if (childResult == null && right != null)
        childResult = right.getNodeReference(label);

    return childResult;

}

一般来说，您应该坐下来，仔细查看您的代码，然后一次执行一行。通常，当你这样做时，这样的问题就会变得清晰。

希望有帮助。