java - java中的递归和跨堆栈维护变量状态

Question

我试图解决 BST 中的一个问题，问题是“检查所有叶子是否都在同一水平”

在这个问题中，我需要不断增加每个堆栈调用的级别，但还要在所有调用中保持一个值，即最大级别。除此之外，我需要返回一个带有结果的 boolean 值。

解决起来很简单，我需要一直往下做，我就是这样做的

int maxlevel = 0;
public boolean allAtSameLevel(Node root, int level){
    if(root== null){
        return false;
    }
    if(root.left== null && root.right == null){
        if(maxlevel == 0){
            maxlevel = level;
        }
        return(level== maxlevel);
    }
    return allAtSameLevel(root.left, level+1) && allAtSameLevel(root.right, level+1) ;
}

我的问题是对于一个需要共享的值，我必须在java中维护一个实例变量。有一个更好的方法吗？我的困惑是，因为它会先一直到右叶然后再上升，所以传递值无济于事。有什么想法吗？

Answer 1

诀窍是将子树的深度传回堆栈的较高层，但只有当左右深度相同时才这样做。您可以使用一个简单的递归函数来完成:

int eqDepth(Node n) {
    if (n == null) return 0;     // This is a leaf, its subtree depth is zero
    int dLeft = eqDepth(n.left); // Make two recursive calls
    int dRight = eqDepth(n.right);
    // If one of the depths is negative, or the depths are different,
    // report it by returning negative 1:
    if (dLeft < 0 || dRight < 0 || dLeft != dRight) return -1;
    return 1+dLeft; // It's the same as dRight
}

有了这个函数，您可以在一行中编写allAtSameLevel:

public boolean allAtSameLevel(Node root) {
    return eqDepth(root) >= 0;
}

这是一个demo on ideone.它从一棵不平衡的树开始，得到一个 -1

     a
   /   \
  b     c
 / \   / \
d   e  f  -

然后添加缺失的节点

     a
   /   \
  b     c
 / \   / \
d   e  f  g

并得到一个积极的结果。