递归 - 二叉树
本文关键字：二叉树 递归 | 更新日期: 2023-09-27 18:30:10
我有这个代码来查找二叉树的直径。二叉树的直径：树的直径(有时称为宽度(是树中两片叶子之间最长路径上的节点数。
我正在尝试理解下面的代码和递归。我正在尝试用这棵简单的树干运行。我知道当根是 20 高度时将变为 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));
}
归是一种基于堆栈的方法。函数的递归调用将在发布者之前执行。如果您考虑函数组合的概念，则可以更轻松地理解递归。让我们看一下这个示例函数调用：
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(我们添加当前节点(是最大高度
这里使用的策略称为分而治之。这由几个阶段组成：- 将任务划分为相似但较小的子任务，直到达到琐碎- 征服结果，逐渐获得更复杂的子任务的响应，直到你得到最初问题的答案
在我们的例子中，简而言之，算法是从根到叶，直到它在所有子树中达到平凡，这是由root == null的结束符号决定的，然后使用琐碎的答案来获得下一个琐碎问题的答案。所以，你要从根到叶子分裂，然后从叶子到根又回来征服。
归你的简单树：
[] <---- root
/ '
[] [] <---- children
最初调用函数时，root == 0将为 true，因此输入高度初始化为 0：
[h=0] <---- root
/ '
[] [] <---- children
然后，您将左右子树的根高度设置为 0：
[h = 0, lh = 0, rh = 0] <---- root
/ '
[] [] <---- children
然后你在左子项上递归，传入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的高度返回给父级，这将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
我们已经在两个子树上递归了，我们回到根，它现在知道它的左右子树的高度(两者都是1(，所以它可以计算：
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
最后一行在这里最重要的：
return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter));
当前树有 3 种情况：
1( 左侧子树中最长的简单路径(用于 currenet 树(
2( 右侧子树中最长的简单路径(用于 currenet 树(
3(最长的简单路径由3部分组成：从最深节点到左子树中根的路径，当前节点，从根到右子树中最深节点的路径。
我们可以递归计算 3 种可能的直径，然后选择其中的最大值。