O(n)中二叉树的直径[C ++中的新方法]？
二叉树的直径是每个节点的（left_height+right_height+1）。因此，在此方法中，我们将为每个节点计算（left_height+right_height+1）并更新结果。时间复杂度保持不变O(n)。
让我们首先定义一个结构，该结构将表示一个包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来我们创建我们的newNode(intdata)该函数接受一个int值并将其分配给该节点的数据成员。该函数将指针返回到创建的结构节点。同样，新创建的节点的左和右子级设置为null。
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}直径（节点*根）函数获取根节点，并检查根节点是否为空。然后，我们使用值INT_MIN定义ans变量。的返回值height(root,ans)存储到height_of_tree变量中。ans从函数返回。
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
}height（Node*root，int＆ans）函数通过引用获取根节点和ans变量。然后，我们在树上执行有序遍历，以计算其每个子树的长度，并在每个递归调用中将ans的maxValue作为第二个参数传递。ans是（ans，1+left_height+right_height）的最大值。
示例
让我们看一下下面的实现来找到二叉树的直径O(n)方法。
#include <iostream>
using namespace std;
struct Node {
int data;
Node* leftChild, *rightChild;
};
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
int height(Node* root, int& ans){
if (root == NULL)
return 0;
int left_height = height(root->left, ans);
int right_height = height(root->right, ans);
ans = max(ans, 1 + left_height + right_height);
return 1 + max(left_height, right_height);
}
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
}
int main(){
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Diameter is %d\n", diameter(root));
return 0;
}输出结果上面的代码将产生以下输出-
Diameter is 4