java - 无法停止递归java

我正在尝试使用标签来搜索节点，并在目标节点下添加一个新节点，
当我尝试使用递归搜索时，它总是返回错误的目标或返回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;
}

最佳答案

如果您实际跟踪代码，则可以很清楚地看到为什么它会返回错误的结果。如果树的第一级的所有子级都不匹配标签，则我在下面标记了代码路径（假定左/中/右全都不为空）：

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;

}

通常，您应该坐下来仔细看一下代码，然后一次浏览一行。通常，当您这样做时，类似的问题就会变得很明显。

希望能有所帮助。