java - 使用递归添加到变量

Question

下面的代码使用私有(private)方法来添加变量计数。该变量下面是条件语句，根据我的理解，在递归堆栈跟踪 upword 之前，这些条件语句不会运行。我对么？我的测试失败了，我想看看是否是因为我的代码错误或者我使用了错误的递归。

public boolean containsRightRedEdge() {
    int count = 0;
    count += containsRightRedEdge(root);
    if(count > 0) return true;
    return false;
}

private int containsRightRedEdge(Node n) {
   if (n == null) return 0;
   if (isRed(n.right)) {
       return 1;
   }
   return containsRightRedEdge(n.left) + 0 + containsRightRedEdge(n.right);         
}

Answer 1

我想说你使用递归几乎是正确的，但是你选择的方法名称可能不会那么困惑，并且你的逻辑可以被简化。我不太熟悉您要实现的算法，但您可以尝试这样的操作:

public boolean containsRightRedEdge(Node root) {
   return getNumRightRedEdges(root) > 0;
}

private int getNumRightRedEdges(Node n) {
   if (n == null) return 0;
   if (isRedEdge(n)) return 1;

   return getNumRightRedEdges(n.left) + getNumRightRedEdges(n.right);
}

通常，递归方法不应与非递归方法同名。这些方法名称更清楚地传达了每个方法的作用。此外，您的基本案例可能是错误的，因为您目前是根据我解释算法应该如何工作来编写它们的。当然，我不知道 isRed() 内部的代码，所以我可能在这里做出了错误的假设。