이진 트리가 주어집니다. 목표는 주어진 트리에서 최대 길이 사이클을 찾는 것입니다. 루트노드에서 왼쪽 서브트리와 오른쪽 서브트리의 최대 높이를 찾아 이를 수행하고 이러한 최대 길이 경로를 결합하여 가장 긴 주기를 얻습니다.
위의 트리에서 최대 길이 주기는 1-2-3-4-7-6 또는 1-6-7-4-3-2-1입니다. 길이는 6입니다.
입력 - 나무
출력 − 최대 길이 주기는 − 5
입니다.설명 − 왼쪽 서브트리의 최대 높이는 3이고 오른쪽 서브트리의 최대 높이는 1입니다. 사이클 길이는 3+1+1=5가 됩니다. 주기는 1-2-3-4-6 또는 1-6-4-3-2입니다.
입력 - 나무
출력 − 최대 길이 주기는 − 7입니다.
설명 − 왼쪽 서브트리의 최대 높이는 3이고 오른쪽 서브트리의 최대 높이는 3입니다. 사이클 길이는 3+3+1=7이 됩니다. 주기는 5-4-2-1-8-7-6 또는 5-6-7-8-1-2-4-5입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
공개 데이터 멤버가 있는 클래스 트리 노드를 만듭니다. 노드의 가중치에 대한 int 데이터, 다른 노드를 가리키는 왼쪽 및 오른쪽 트리 노드 포인터입니다.
-
함수 newNode(int data)는 데이터를 매개변수로 받아 왼쪽 및 오른쪽 포인터가 NULL인 노드를 생성합니다.
-
newnode() 함수를 호출하여 트리를 생성합니다.
-
함수 maxheight(treenode* root)는 트리의 루트를 가져와 루트에 있는 트리의 최대 높이를 반환합니다.
-
이 함수는 루트가 NULL인지 확인하고 높이가 0임을 의미하고 0을 반환합니다.
-
lheight 및 rheight는 maxheight(root->left)에 대한 재귀 호출을 통해 노드 루트의 왼쪽 및 오른쪽 하위 트리 높이를 계산합니다. 및 최대 높이(루트->오른쪽);
-
높이와 높이를 비교하여 얻은 최대값을 반환합니다.
-
main 내부에는 treeNode의 왼쪽 서브트리와 오른쪽 서브트리의 최대 높이 값을 저장합니다.
-
이제 최대 길이 주기는 루트 자체를 포함하여 최대 높이 + 최대 높이+1의 합계입니다.
-
결과적으로 주기의 길이를 인쇄하십시오.
예시
#include <bits/stdc++.h>
using namespace std;
//class for tree
class treenode{
public:
int data;
treenode* left;
treenode* right;
};
//find maximum height between left and right subtree of current root
int maxheight(treenode* root){
if (root == NULL)
return 0;
else{
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
//find maximum height
if (lheight > rheight)
return(lheight + 1);
else
return(rheight + 1);
}
}
//creating a node of tree
treenode* newNode(int data){
treenode* Node = new treenode();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main(){
treenode *root = newNode(6);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(7);
root->left->right->right->left = newNode(2);
int maxlheight=maxheight(root->left);
int maxrheight=maxheight(root->right);
int maxlheight=maxDepth(root->left);
int maxrheight=maxDepth(root->right);
cout << "Maximum length cycle: " << maxlheight+maxrheight+1;
return 0;
} 출력
Maximum length cycle: 6