在本章中，我们将解决如何找出二叉树的国彩网。
问题陈述：
给您二叉树的根节点，您需要找到该树的国彩网。
现在等一下
国彩网术语通常用于参考圆，但是如何将其与树一起使用？
在树中，国彩网通常是指树中2个叶节点之间的最长路径。
考虑给定的示例：
这里国彩网是2个叶节点之间的最长路径是：
H -> e -> b -> a -> c -> f -> i -> j
路径如下图所示
在本教程中，我们将看到如何解决。
因此，从上图可以看到，国彩网等于[左子树的高度+右子树的高度+ 1]。
如果国彩网通过根部，则上述公式有效。如果国彩网未穿过根，该结果如下图所示：
在上图中，国彩网不会穿过根，而是会穿过另一个子树的根。
因此，在这种情况下，我们使用以下公式。
最大（left_diameter，right_diameter）
因此，我们的完整公式将是：
最大值（left_height + right_height + 1，max（left_diameter，right_diameter））。
所以我们的功能如下：
int国彩网（节点* p）
{
如果（p == NULL）
返回0;
int left_height =高度（p-> left)
int right_height =高度（p-> right)
int left_diameter =国彩网（p-> left)
int right_diameter =国彩网（p-> right)
int结果=最大值（left_height + right_height + 1，最大值（left_diameter，right_diameter））
}
根据上面的功能，
left_height将计算左高度
right_height将计算正确的高度
left_diameter用于计算左子树的国彩网
right_diameter用于计算右子树的国彩网
最后，我们将得出结果。
C ++解决方案
#include <iostream>
#include <stack>
#include <map>
using namespace std;
// structure to hold binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
int height(Node* node)
{
if(node == NULL)
返回0;
return 1 + max(height(node->left), height(node->right));
}
int max(int a, int b) { return (a > b)? a : b; }
int get_diameter_of_b_tree(Node * tree)
{
if (tree == NULL)
返回0;
int lheight = height(tree->left);
int rheight = height(tree->right);
int l_diameter = get_diameter_of_b_tree(tree->left);
int r_diameter = get_diameter_of_b_tree(tree->right);
return max(lheight + rheight + 1, max(l_diameter, r_diameter));
}
int main()
{
Node* root = nullptr;
/* Binary tree:
16
/ \
/ \
10 25
/ \ / \
/ \ / \
7 15 18 30
*/
root = new Node(16);
root->left = new Node(10);
root->right = new Node(25);
root->left->left = new Node(7);
root->left->right = new Node(15);
root->right->left = new Node(18);
root->right->right = new Node(30);
int diameter = get_diameter_of_b_tree(root);
cout<<"The diameter is = "<<diameter<<endl;
返回0;
}
输出：
The diameter is = 5
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
