二叉树最大高度的递归代码

Question

我遇到了一个计算二叉树最大高度的递归代码-

int maxDepth(struct node* node)
{
  if (node==NULL)
     return 0;
  else
   {
     /* compute the depth of each subtree */
     int lDepth = maxDepth(node->left);
     int rDepth = maxDepth(node->right);

     /* use the larger one */
     if (lDepth > rDepth)
       return(lDepth+1);
    else return(rDepth+1);
   }
}

我尝试用另一种方式编写代码-

    int maxDepth(struct node* node)
 {
    if (node==NULL)
     return 0;
    else
    {
     /* compute the depth of each subtree */
     int lDepth = 1+maxDepth(node->left);  //notice the change
     int rDepth = 1+maxDepth(node->right); //notice the change

     /* use the larger one */
     if (lDepth > rDepth)
       return(lDepth);
    else return(rDepth);
   }
}

我很困惑这两个版本的工作方式是否相似，或者在第二个实现中是否存在错误。我尝试了几个案例，两个函数返回相同的结果。

Answer 1

这两个 C 函数的行为相同。在重写函数 maxDepth() 时，您所做的就是将变量 lDepth 和 rDepth 加 1。但是，您可以通过从 return 值中的这些变量中减去 1 来有效地撤消该更改：

int lDepth = 1+maxDepth(node->left);  // you added one to lDepth
int rDepth = 1+maxDepth(node->right); // you added one to rDepth

/* use the larger one */
if (lDepth > rDepth)
  return(lDepth);                     // but you subtract one here
else return(rDepth);                  // and you also subtract one here

Answer 2

在算术上它们是相同的，将 1 添加到答案中并不重要，因为没有对返回的值进行其他算术转换。从技术上讲，你的效率稍低，因为你做了两次加法，然后丢弃了两个值中较小的一个，这浪费了在那个值上所做的工作。实际上，我怀疑如果你做计时，你是否会注意到差异。

二叉树最大高度的递归代码

Recursive code for maximum height of a binary tree

tree

recursion