C ++のO（n）[新しいメソッド]の二分木の直径？

二分木の直径は、各ノードの（left_height + right_height + 1）です。したがって、このメソッドでは、ノードごとに（left_height + right_height + 1）を計算し、結果を更新します。ここでの時間計算量はO（n）のままです。

まず、データとその左右のノードの子を含むツリーノードを表す構造体を定義しましょう。これが最初に作成されるノードの場合はルートノード、それ以外の場合は子ノードです。

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

次に、int値を取得してノードのデータメンバーに割り当てるnewNode（int data）関数を作成します。この関数は、作成された構造体ノードへのポインターを返します。また、新しく作成されたノードの左右の子はnullに設定されます。

struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

Diameter（Node * root）関数は、ルートノードを取得し、ルートノードがnullかどうかをチェックします。次に、値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が各再帰呼び出しの2番目のパラメーターとして渡されます。 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