在1个变形的程序中查找二进制搜索树的高度

Question

用于查找BST高度的此实现：

int findHeight1(treeNode_type*root)
{
  if(root==NULL)
      return -1;
   else
   {
      return max(findHeight1(root->left),findHeight1(root->right))+1;
   }
}

但这不是：

int findHeight(treeNode_type*root)
{
   if( root->left==NULL && root->right==NULL)//current node on stack frame is leaf node
      return 0;
   else
   {
      return max(findHeight(root->left),findHeight(root->right))+1;
   }
}

这两个实现的基本情况逻辑对我来说都是合理的，但是为什么后者不起作用。

优惠，但以防万一：

typedef struct treeNode_type treeNode_type;

struct treeNode_type
{
   int data;
   treeNode_type *left;
   treeNode_type *right;
};

Answer 1

^{将评论转移到答案。}] >>

[在第二种情况下，当节点是叶节点时，树的高度为1，而不是0。而且，第二种情况似乎无法处理左指针不为空而右指针为零的情况。 't，反之亦然。

您可以使用：

int findHeight(treeNode_type*root)
{
   if (root == NULL)
      return 0;
   else if (root->left == NULL && root->right == NULL)
      return 1;
   else
   {
      return max(findHeight(root->left), findHeight(root->right)) + 1;
   }
}
尚不清楚与较简单的第一版代码相比，是否有明显的好处，尽管这样做确实避免了对叶节点的两次递归调用。您可以在else子句之前添加以下条件和测试：

   else if (root->left == NULL)
      return findHeight(root->right) + 1;
   else if (root->right == NULL)
      return findHeight(root->left) + 1;
再次，目前尚不清楚是否会大大加快处理速度；额外的条件甚至可能使CPU管道停滞并减慢速度。