递归 - 二叉树

Question

我有这个代码来找到二叉树的直径。 二叉树的直径：树的直径（有时称为宽度）是树中两棵树叶之间最长路径上的节点数。

我想了解下面的代码和一般的递归。我试图用这个简单的树干运行。我明白什么时候root的高度会变成1（Max（0,0）+1），然后返回Math.Max（0 + 0 + 1，Max（0,0））。我的理解是，它将根据此返回值将ldiameter设置为1，而root = 10。这是正确的吗？此时lh变为1.它如何变为1？另外，如果你可以帮助我干一步一步地运行这个简单的树，这将是非常有用的。

10 
/ \ 
20 30 


public int FindDiameter_util(Node root, ref int height) 
     { 
      /* lh --> Height of left subtree 
      rh --> Height of right subtree */ 
      int lh = 0, rh = 0; 

      /* ldiameter --> diameter of left subtree 
       rdiameter --> Diameter of right subtree */ 
      int ldiameter = 0, rdiameter = 0; 
      if (root == null) 
      { 
       height = 0; 
       return 0; /* diameter is also 0 */ 
      } 
      /* Get the heights of left and right subtrees in lh and rh 
       And store the returned values in ldiameter and ldiameter */ 
      ldiameter = FindDiameter_util(root.left, ref lh); 
      rdiameter = FindDiameter_util(root.right, ref rh); 

      /* Height of current node is max of heights of left and 
       right subtrees plus 1*/ 
      height = Math.Max(lh, rh) + 1; 

      return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter)); 
     } 

Answer 1

最后行最重要的位置：

return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter)); 

有3例为当前的树：

1）最长简单路径（在currenet树）在左子树

2）右子树中最长的简单路径（用于currenet树）

3）lo最简简单路径由3部分组成：从左边子树中最深的节点到根节点的路径，当前节点，右边子树中从根节点到最深节点的路径。

我们可以递归计算3个可能的直径，然后选择它们的最大值。

Answer 2

让我们通过您简单的树递归：

[]  <---- root 
/ \ 
[] [] <---- children 

当函数最初叫，root == 0将是真实的，所以输入高度被初始化为0：

[h=0]  <---- root 
/ \ 
    [] [] <---- children 

然后你会设置左侧和右侧子树根部的高度为0：

[h = 0, lh = 0, rh = 0]  <---- root 
     / \ 
     []  []   <---- children 

然后y OU递归左边的孩子，在lh通过其高度参数：

[h = 0, lh = 0, rh = 0]  <---- root 
     / \ 
     [h=0] []   <---- children 

左子将初始化其高度的变量为自己的左，右子树：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

然后左子会尝试在自己的左子树上进行递归（即使没有一个子树;这是null）：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 
     /
     null 

在这个空节点，我们承认它是这样，返回0，走回到父，lh被设置为0（再次，所以没有变化）：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

然后我们递归的右子树，但它也为空：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 
       \ 
      null 

所以我们返回0 FO [R其高度父，这台rh到0（再次）：

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

到目前为止，颇为无趣。但是现在我们知道了子树的高度，我们可以计算当前树的高度为max(lh, rh) + 1，这给了我们这个叶子的高度为1（一棵只有根的树的高度为1，所以它是有意义的一个只有根的子树具有高度1）。

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=1, lh=0, rh=0] []   <---- children 

然而，h在这个水平实际上是在根lh的引用，所以它也成为1：

 [h = 0, lh = 1, rh = 0]  <---- root 
      /  \ 
    [h=1, lh=0, rh=0] []   <---- children 

现在左子树做，所以我们递归右侧子树以同样的方式（详细内容略）：

  [h = 0, lh = 1, rh = 1]   <---- root 
      /    \ 
    [h=1, lh=0, rh=0] [h=1, lh=0, rh=0] <---- children 

现在，我们已经递归两个子树，我们返回到根，现在谁知道

height = Math.Max(lh, rh) + 1; 

是

height = Math.Max(1, 1) + 1 = 2 

所以根得到其高度设定为2：

  [h = 2, lh = 1, rh = 1]   <---- root 
      /    \ 
    [h=1, lh=0, rh=0] [h=1, lh=0, rh=0] <---- children 

其左和右子树（均为 1），因此它可以计算的高度

Answer 3

递归是一种基于堆栈的方法。函数的递归调用将比发行者更早执行。如果您考虑函数组合的概念，您可以更容易理解递归。让我们来看看下面这个例子函数调用：

f(g(x)) 

正如你所看到的，f参数是g(x)，这意味着一个执行f(g(x))前g(x)需要首先计算，因此g(x)是f(g(x))的依赖。现在，假设g是f一样，所以你打电话

f(f(x)) 

以类似的方式，f(x)是f(f(x))的依赖，因为你不能没有具有f(x)结果计算f(f(x))。

如果你明白这个纯粹的数学概念，那么下一步就是将算法添加到f作为上下文。在编程中，f(f(x))不一定只是一个计算，但可能会发生一些状态更改。

下一步是了解重复递归的概念。在我们的情况下，我们不知道应该在FindDiameter_util之内调用FindDiameter_util多少次，因为它适用于任何树。所以，让我们稍微分析一下这个功能。

事实：

• 叶节点的事实，root == null，这是结束标志以及识别（参见return）
• 高度叶节点中的0
• 在非琐碎的情况下，当节点不是叶节点，任务分为两个子任务（左子树和右子树）
• 当计算的子任务的结果，那么子大树+ 1（我们加上当前节点）的树是最大h八

这里使用的策略叫做Divide et Impera。这是由以下几个阶段组成： - 划分任务成相似，但更小的子任务，直到你到达平凡 - 征服的结果，得到响应，逐步更复杂的子任务，直到你得到的回答最初的问题

在我们的例子中，算法总之是从根到叶子，直到在所有子树中达到平凡，这是由root == null的结束符号决定的，然后使用平凡的答案来得到答案到下一个微不足道的问题。所以，你要从根到叶去划分，然后从叶子到根部去征服。