이진 트리의 지름은 각 노드의 (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