สมมติว่าเรามีต้นไม้ไบนารี งานของเราคือนับทรีย่อยที่มีค่าเดียวในทรีที่กำหนด ทรีย่อยที่มีค่าเดียวคือทรีย่อย โดยที่โหนดทั้งหมดของทรีนั้นมีค่าเท่ากัน สมมติว่าต้นไม้เป็นเหมือนด้านล่าง −
มีสี่ทรีย่อยค่าเดียว เหล่านี้เป็นเหมือนด้านล่าง −
เราสามารถแก้ไขได้โดยใช้วิธีการจากล่างขึ้นบน สำหรับทุกทรีย่อยที่เข้าชม ให้คืนค่า จริง หากทรีย่อยที่รูทภายใต้นั้นมีค่าเดียว และเพิ่มตัวนับ 1 ในที่นี้ การนับคือพารามิเตอร์อ้างอิงสำหรับการเรียกซ้ำ และใช้ค่าที่ส่งคืนเพื่อดูว่าทรีย่อยซ้ายและขวามีค่าเดียวหรือไม่
ตัวอย่าง
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left, *right;
};
Node* getNode(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool countSingleValuedSubtree(Node* root, int &count) {
if (root == NULL)
return true;
bool left = countSingleValuedSubtree(root->left, count);
bool right = countSingleValuedSubtree(root->right, count);
if (left == false || right == false)
return false;
if (root->left && root->data != root->left->data)
return false;
if (root->right && root->data != root->right->data)
return false;
count++;
return true;
}
int countSingleValSubtree(Node* root) {
int count = 0;
countSingleValuedSubtree(root, count);
return count;
}
int main() {
Node* root = getNode(5);
root->left = getNode(1);
root->right = getNode(5);
root->left->left = getNode(5);
root->left->right = getNode(5);
root->right->right = getNode(5);
cout << "Count of Single Valued Subtrees is: " << countSingleValSubtree(root);
} ผลลัพธ์
Count of Single Valued Subtrees is: 4
