เราได้รับ Binary Tree เป้าหมายคือหาวงจร (cycle) ยาวที่สุดในต้นไม้ โดยการหาความสูงสูงสุดของ subtree ซ้ายและขวาจาก root แล้วนำ path สูงสุดทั้งสองมาต่อกันเพื่อได้ longest cycle
สำหรับต้นไม้ข้างต้น longest cycle คือ 1-2-3-4-7-6 หรือ 1-6-7-4-3-2-1 ความยาว 6
อินพุต − ต้นไม้
เอาต์พุต − Maximum length cycle is − 5
คำอธิบาย − ความสูงซ้าย = 3, ขวา = 1 Cycle length = 3+1+1=5 (รวม root)
อินพุต − ต้นไม้
เอาต์พุต − Maximum length cycle is − 7
คำอธิบาย − ความสูงซ้าย = 3, ขวา = 3 Cycle length = 3+3+1=7
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- สร้าง class treenode มี data, left, right pointer
- ฟังก์ชัน newNode(int data) สร้างโหนดใหม่ left, right = NULL
- สร้างต้นไม้ด้วย newNode()
- ฟังก์ชัน maxheight(treenode* root) คืนค่าความสูงสูงสุดของต้นไม้ที่ root
- ถ้า root == NULL คืน 0
- lheight, rheight เรียกซ้ำ maxheight(root->left), maxheight(root->right)
- คืนค่า max(lheight, rheight) + 1
- ใน main เก็บ maxlheight และ maxrheight ของ root
- Maximum length cycle = maxlheight + maxrheight + 1
- พิมพ์ความยาววงจร
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class treenode {
public:
int data;
treenode* left;
treenode* right;
};
int maxheight(treenode* root) {
if (root == NULL)
return 0;
else {
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
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);
cout << "Maximum length cycle: " << maxlheight + maxrheight + 1;
return 0;
}
ผลลัพธ์
Maximum length cycle: 6
