Как рекурсия работает в этом методе?

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

То, что вы хотите сделать, это итерация в подузлы с рекурсивным вызовом. Например:

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

Answer 2

При вызове return fullHelper(node); вы перерабатываете тот же самый узел, с которого вы начали метод.Предполагая, что установлены и node.left, и node.right, это приведет к бесконечному рекурсивному вызову и StackOverflowException.

Вам необходимо выполнить рекурсию до левого и правого подузлов, чтобы проверить их так же, как вы только что проверили текущий узел, например, вы можете заменить проблемную строку на:

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