你如何通过两个 return 语句递归？ [JAVA]

Question

我目前正在尝试实现二叉搜索树形状比较，但我的一行代码遇到了问题。

    if(treeStructOne.getHeight() == 1 && treeStructTwo.getHeight() == 1) //Base Case, if both are empty then they must be equal!
    {
        return true;
    }
    if(treeStructOne.getHeight()  != treeStructTwo.getHeight()) //First make sure height is the same, if not, must be unequal
    {
        return false;
    }
        if(treeStructOne.hasLeft()  && treeStructTwo.hasLeft())
        {
            return similar(treeStructOne.getLeft(),treeStructTwo.getLeft());

        }
        if(treeStructOne.hasRight() && treeStructTwo.hasRight()) //PROBLEM IS HERE
        {
            return similar(treeStructOne.getRight(),treeStructTwo.getRight());  
        }        
        return false;

当树 1 和树 2 上的节点有左节点 child，但只有树 1 有右节点而树 2 没有。在检查它们都已离开后 child ren，它不会运行右边的检查 children 如果左边是真的。这与递归在 java 中的工作方式有关吗？

Answer 1

如果两棵树的 hasLeft() return 都为真，那么您的方法将在该 if 子句中 return。我的猜测是您想在最后两个 if 子句中分配类似调用的结果，并在 if 子句之后执行类似

的操作

return leftSimilar && rightSimilar;

Answer 2

前两个 if 会起作用，但最后一部分应该捕获 p 隐含 q 的条件，即左右都为 ~p 或 q。换句话说，如果treeStructOne有一个左子树，treeStructTwo有一个左子树，那么检查它们是否相似（return相似...）

if(treeStructOne.getHeight() == 1 && treeStructTwo.getHeight() == 1) //Base Case, if both are empty then they must be equal!
    {
        return true;
    }
if(treeStructOne.getHeight()  != treeStructTwo.getHeight()) //First make sure height is the same, if not, must be unequal
    {
        return false;
    }
return (treeStructOne.hasLeft() && treeStructTwo.hasLeft()
         ? similar(treeStructOne.getLeft(),treeStructTwo.getLeft())
         : false)
    && (treeStructOne.hasRight() && treeStructTwo.hasRight()
         ? similar(treeStructOne.getRight(),treeStructTwo.getRight())
         : false);

Answer 3

return语句立即returns来自当前方法，即方法的其余部分将不会被执行。

在您的情况下，您希望在从方法返回之前进行两次递归调用。你可以这样做：

boolean similarLeft;
if(treeStructOne.hasLeft()  && treeStructTwo.hasLeft()) {
    similarLeft = similar(treeStructOne.getLeft(),treeStructTwo.getLeft());
} else {
    similarLeft = ?; // TODO what is good condition here?
}

然后对右侧做同样的事情并以

结束

return similarLeft && similarRight;

然而，对于真正的思想 java，我会在调用方法之后而不是之前进行空值检查，从而减少代码重复：

boolean similar(TreeStruct x, TreeStruct y) {
    if (x == null) {
        return y == null;
    } else {
        return y != null && similar(x.left, y.left) && similar(x.right, y.right);
    }
}

你如何通过两个 return 语句递归？ [JAVA]

How do you recurse through two return statements? [JAVA]

java

recursion

binary-search-tree