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 데이터) 함수를 만듭니다. 함수는 생성된 구조체 노드에 대한 포인터를 반환합니다. 또한 새로 생성된 노드의 왼쪽과 오른쪽 자식은 null로 설정됩니다.

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

직경(Node* root) 함수는 루트 노드를 가져와 루트 노드가 null인지 여부를 확인합니다. 그런 다음 값이 INT_MIN인 as 변수를 정의합니다. height(root, as)의 반환 값은 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) 함수는 루트 노드와 as 변수를 참조로 받습니다. 그런 다음 트리에서 중위 순회를 수행하여 각 하위 트리 길이를 계산하고 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