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);

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

Answer 1

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

您需要递归到左右子节点来检查它们，就像检查当前节点一样，例如您可以将有问题的行替换为:

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