java - 在这种方法中递归是如何工作的？

Question

我正在编写一种方法来查找二叉树是否已满，这是我目前所拥有的：

    public boolean full(){
    return fullHelper(this);
}

public boolean fullHelper(BinaryTreeNode<T> node){
    if (node == null){return false;}
    if (node.left == null && node.right == null){return true;}
    if (node.left != null && node.right != null){
        return fullHelper(node);
    }
    return false;
}

您传入的节点可以是根节点，也可以是某个任意节点，用于检查子树是否已满。我的方法一直卡在线上

return fullHelper(node);

我想知道为什么它不会通过它上面的线来检查两个孩子是否都为空。我对二叉树和一般的递归都很陌生，所以如果有人能帮助解释我所做的任何错误假设，我将不胜感激！

Answer 1

通过调用return fullHelper(node);您正在重新处理您启动该方法的同一节点。假设同时设置node.left和node.right，这将导致无限递归调用和StackOverflowException.

您需要对左右子节点进行递归，以检查它们的方式与您刚刚检查当前节点的方式相同，例如，您可以将有问题的行替换为：

return fullHelper(node.right) && fullHelper(node.left);

Answer 2

您想要做的是使用递归调用迭代到子节点。例如：

if (node.left != null && node.right != null) {
    return fullHelper(node.left) && fullHelper(node.right);
}