java - 堆栈溢出二叉搜索树计算深度

Question

我正在尝试计算二叉搜索树中键的深度，但出现堆栈溢出错误，但我不确定原因。这是我当前的代码。

private int calcDepth( Tree<K, V> x, K keyIn, int currentLevel){ 
  //BASE CASE  
  if (this.key.compareTo(keyIn) == 0) return currentLevel; 

  if (this.key.compareTo(keyIn) < 0){ 
     return calcDepth(this.left, keyIn, currentLevel+1);  
  }

  if (this.key.compareTo(keyIn) > 0){ 
     return calcDepth(this.right, keyIn, currentLevel + 1); 
  }

  return -1; 
}

这是我的算法

//ALGORITHIM 
//1. if the current key is equal to the parameter key 
//   return the currentLevel 
//2. if the current key is less than the parameter key 
//   go left and increment the level 
//3. if the current key is greater than the paramete key 
//   go right  and increment the level 
//4. if none of these cases are met (key is not in tree
//   return -1 

我是java新手，所以请原谅这个问题的初学者水平

Answer 1

I am getting a stack overflow error and I'm not sure why

这是因为，您始终将 this.left 和 this.right 作为参数传递给该方法calcDepth 始终相同。此外，this.key 始终相同，因此本质上您始终比较两个键(this.key 和 keyIn)，而不实际遍历树。即它应该是:

if (x.key.compareTo(keyIn) == 0) 

然后当你调用时:

calcDepth(x.left, keyIn, currentLevel+1); 

或

calcDepth(x.right, keyIn, currentLevel + 1);

x 是每次调用该方法时的不同实例。

看来您没有对参数 x 执行任何操作。您应该使用 x.key (其中 x表示树的当前实例)。

现在，x.left 和 x.right 在每次调用该方法时都会有所不同，因此本质上我们正在缩小问题范围并达到基本情况，因此该方法将能够返回到调用方法并最终结束，而不会出现 StackOverflow 异常。

最后但并非最不重要的一点是，您的代码中存在一个额外的错误，如果给定的 key 不存在，算法将无法返回 -1。要解决这个问题，只需插入一个条件来检查当前的树是否为空，如果我们没有找到key，我们可以简单地返回 -1。

注意 - 这也将防止出现 NullPointerException 的可能性。

private int calcDepth( Tree<K, V> x, K keyIn, int currentLevel){ 

  if(x == null) return -1; // key doesnt exist if this is true

  if (x.key.compareTo(keyIn) == 0) return currentLevel;  //BASE CASE  

  if (x.key.compareTo(keyIn) < 0){   // check left tree
      return calcDepth(x.left, keyIn, currentLevel+1);  
  }

  if (x.key.compareTo(keyIn) > 0){  // check right tree
      return calcDepth(x.right, keyIn, currentLevel + 1); 
  }

  return -1; 
}