时间戳

首页 > 解决方案 > 我的实现树的高度有什么问题？

c++ - 我的实现树的高度有什么问题？

问题描述

我正在做一些运动

https://practice.geeksforgeeks.org/problems/height-of-binary-tree/1

这是已经使用的输入格式。 在此处输入图像描述

我看到他们的实现有遍历的节点数而不是边数。所以，我在我的答案中加了 1 来弥补这一点。但是，我的回答是因为他们的输入“5 5 N 4 10 N 8 5 N 8 8 N 6”而失败，我不明白它是如何失败的。我信心不足，想知道我是否做错了什么来找出这里树的高度。

int result1 = 0;
int result2 = 0;
int MyHeight(Node *root)
{
   if(root->left == NULL && root->right == NULL)
   {
       return 0;
   }

   if(root->left)
   {
     //cout<<"Executing root->left = data = "<<root->data<<endl;
     result1 =  MyHeight(root->left) + 1;
     //cout<<"height -left --of .."<<root->data<<" = "<<result1<<endl;
   }
   if(root->right)
   {
     result2 = MyHeight(root->right) + 1;
     //cout<<"right.height of .."<<root->data<<" = "<<result2<<endl;
   }
   if(result1 > result2)
       return result1;
   return result2;
}

int get_Height(Node* root)
{
  // Your code here
  //cout<<"root->data"<<root->data;
  return MyHeight(root);   
}

在什么情况下，这个实现会失败？你能在它会失败的场景中画一棵树吗？我已经调试过了，我看不出那里出了什么问题。这听起来像是他们拥有的无效 BST，但我想知道我的实现是否正确。我看不出它实际上是错误的。

标签： c++data-structures

解决方案

递归和全局变量不能很好地混合。您在每个递归调用中不断覆盖这些全局变量。

具体result2 = MyHeight(root->right) + 1;可以覆盖result1，使其root->left不再是 的高度，而是 的高度root->right->left。解释递归是相当棘手的，最好把你的调试器拿出来，单步调试你的代码，看看如何result1改变result2。

全局变量应始终小心使用，在这种情况下，根本没有理由使用全局变量，makeresult1和result2local toMyHeight应该可以解决您的问题。

推荐阅读