使用静态变量跳出递归

Question

目的：判断一棵树是否为平衡二叉树。

我已经实现了一个可以运行的程序，但我想通过防止不必要的递归来提高它的效率。为此，我使用了一个静态变量，即使在单个条件被评估为 false 时也会设置该变量，以便在进行任何其他递归调用之前 returns，然后再进行自己的递归调用。

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

问题是即使没有条件导致静态变量以某种方式被设置。即，shouldIExit 设置为 1，即使对应的 if 条件不计算为真。

这是我不明白静态变量是如何工作的吗？

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 和 isBalanced 的逻辑，您可以节省一些工作。我相信这样的事情应该有效：

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
    }
}

使用静态变量跳出递归

Using a static variable to break out of recursion

java

recursion

static-variables