Багги в 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;
   }
}

Логика базового варианта обеих реализаций c мне кажется правильной но почему последний не работает.

Тривиально, но на всякий случай:

typedef struct treeNode_type treeNode_type;

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

Answer 1

^{Передача комментария к ответу.}

Во втором случае, когда узел является листовым узлом, высота дерева равна 1, а не 0. Кроме того, второй случай, по-видимому, не соответствует сценарию, в котором левый указатель не равен нулю, а правый - нет, или наоборот.

Вы можете использовать:

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;

Опять же, не ясно, значительно ли это ускорит обработку; дополнительные условия могут даже остановить конвейер ЦП и замедлить его.