c - 找出 BST 的叶子是否在同一层终止

Question

我正在处理 BST，我想编写一个函数来检查所有叶节点是否在同一层终止。

我的第一个想法是获取左子树和右子树的高度，看看它们是否相等，但我意识到这是一个错误的方法，因为我可能遇到这样一种情况，即根的右子树可以为空，而左子树上的叶子在同一层终止。

现在我有点迷失了如何解决这个问题。

我的代码

int isCompleteBst(struct tree *t)
{
  if(t->root == NULL)
  {
    return 0;
  }
  else
  {
    return isCompleteBst_r(t->root);
  }
}
int isCompleteBst_r(struct leaf *lf)
{
   if(geHeight(lf->left) == getHeight(lf->right))
   {
     return 1;
   }
   else
   {
     return 0;
   }
}

Answer 1

首先获取任意一片叶子的深度并存储。它将用于比较。

然后遍历树:

如果您发现一个节点的两个子节点都有效，则在两个节点中继续递归。

如果您命中了一个左右子节点都为 NULL 的节点，则您找到了叶子，将当前深度与存储的深度进行比较。如果不匹配，则停止递归并返回 false。否则继续对左右 child 进行递归。

如果你命中一个有一个子节点 NULL 和一个有效的节点，停止递归，因为深度显然不匹配，并返回 false。

如果您从未遇到错误条件，则默认返回 true。