O(n)中二叉树的直径[C ++中的新方法]？

二叉树的直径是每个节点的（left_height + right_height + 1）。因此，在此方法中，我们将为每个节点计算（left_height + right_height + 1）并更新结果。时间复杂度保持不变O(n)。

让我们首先定义一个结构，该结构将表示一个包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

接下来我们创建我们的 newNode(int data)该函数接受一个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