Использование статической переменной для выхода из рекурсии

Question

Цель: найти, является ли дерево сбалансированным двоичным деревом.

Я реализовал программу, которая работает, но хотел сделать ее более эффективной, предотвращая ненужную рекурсию.Для этого я использую статическую переменную, которая устанавливается, когда даже одно условие оценивается как ложное, так что каждый другой рекурсивный вызов возвращается, прежде чем делать какой-либо из своих собственных рекурсивных вызовов.

static int shouldIExit=0;
public boolean isBalanced(TreeNode root) {
    if(root==null){
        return true;
    }
    if(shouldIExit==1 || Math.abs(height(root.left)-height(root.right))>1){
        height(root.right))>1: "+ (Math.abs(height(root.left)-height(root.right))>1) ) ;
        shouldIExit=1;
        return false;
    }
    else{
     return (isBalanced(root.left) && isBalanced(root.right) );   
    }
}

Проблема в том, что статическая переменная каким-то образом устанавливается, даже если никакие условия не приводят к этому.то есть, должен лиIEIExit = 1, даже если соответствующее условие if не оценивается как true.

Неужели я не понимаю, как работают статические переменные?

Answer 1

Вам не нужна переменная static.Обычно плохая практика - использовать нелокальные переменные (либо static, либо переменные экземпляра) в рекурсивном методе.

public boolean isBalanced(TreeNode root) {
    if(root==null) {
        return true;
    }
    if(Math.abs(height(root.left)-height(root.right))>1) {
        return false;
    } else{
     return (isBalanced(root.left) && isBalanced(root.right) );
    }
}

Вы можете сэкономить некоторую работу, если объедините логику height и * 1007.*.Я считаю, что-то вроде этого должно работать:

public boolean isBalanced (TreeNode root) {
    return balancedHeight(root) >= 0;
}

public int balancedHeight (TreeNode root) {
    if (root == null) {
        return 0; // an empty tree is balanced
    }
    int left = balancedHeight(root.left);
    if (left < 0) {
        return -1; // left sub-tree is not balanced, so entire tree is not balanced
    }
    int right = balancedHeight(root.right);
    if (left == right) { // the tree is balanced if both sub-trees are balanced 
                         // and both have same height
        return left + 1;
    } else {
        return -1; // tree is not balanced - either the right sub-tree is not
                   // balanced or the two sub-trees have different heights
    }
}