C++ 二叉树的直径

在本文中，您将通过示例了解 C++ 中二叉树的直径。

连接二叉树中任意两个节点之间最长路径的边数使我们能够计算二叉树的直径。二叉树的直径是常用来描述其宽度的度量。所走的路径取决于二叉树的直径，并且可能遍历或不遍历二叉树的根。路径中有两个叶节点，每个叶节点的直径都可以计算出来。确定表示二叉树直径的两个节点之间最长路径有两种可能性

• 使用根节点：它将遍历二叉树的根节点并计算根节点。
• 不使用根节点：在此示例中，所选路径不会经过二叉树的基节点，也不会将其包含在路径中。

方法 1

树 T 的直径测量值是以下各项中的最大值

• 左子树的长度
• 右子树的长度
• 连接叶子并通过 T 的根 的最长路径（使用 T 的子树高度计算）

文件名：DiameterOfbtree.cpp

输出

The diameter  is 4

方法 2

高效方法

您可以使用以下方法来解决该问题

通过在同一迭代中计算高度而不是独立调用 heightoftree() 函数，可以改进上述实现。

输出

The diameter of the given binary tree is 4

方法 3：使用 Morris 遍历算法

Morris 遍历算法 通过将左子树的最右节点链接到其父节点来修改二叉树的结构。它允许您遍历树，而无需占用额外的堆栈或递归函数空间。

要将上述想法付诸实施，请按照以下步骤操作

• 使用初始化为二叉树根的 current_node 来遍历二叉树。
• 如果 current_node 不为 NULL，则执行上一步。
• 如果所选节点的左子节点为 NULL，则继续访问右子节点。
• 如果当前所选节点的左子节点不为 NULL，则在当前节点的左子树中找到最右侧的节点。
• 当最右侧元素的右子节点为 NULL 时，将其设置为当前所选节点，并继续访问当前节点的最左侧元素。
• 如果最右侧节点中存在右子节点且不为 NULL，则访问当前节点并继续访问右子节点。
• 使用 maximum 函数，确定每个已访问节点的左右子树高度，然后将直径更新为子树高度与现有直径之和的最大值。
• 返回 直径

文件名：Morris_Traversal.cpp

输出

The diameter is 4

复杂度

时间复杂度：O(N)，其中 N 表示二叉树中的节点总数。

空间复杂度：O(h)，Morris 遍历 的辅助空间复杂度为 O(1)，因为它不使用额外的结构（如 堆栈 或 队列）。另一方面，程序的递归堆栈增加了空间复杂度，导致 O(h)，其中 h 是二叉树的高度。