বাইনারি ট্রির টিল্ট হলো প্রতিটি নোডের বাম ও ডান সাবট্রির সমষ্টির পার্থক্যের абсолют ভ্যালু। সব নোডের টিল্টের যোগফল বের করতে হবে।
উদাহরণ
ট্রি: রুট=৪, বাম=২ (৩,৫), ডান=৯ (null, ৭)
- নোড ৩,৫,৭: টিল্ট=০ (লিফ)
- নোড ২: |৩-৫| = ২
- নোড ৯: |০-৭| = ৭
- নোড ৪: |(৩+৫+২) - (৯+৭)| = |১০-১৬| = ৬
- টোটাল টিল্ট = ২+৭+৬ = ১৫
অ্যালগরিদম (পোস্ট-অর্ডার DFS)
- রিকার্সিভ ফাংশন যা সাবট্রির সমষ্টি রিটার্ন করে।
- গ্লোবাল/রেফারেন্স ভেরিয়াবলে টিল্ট যোগ করুন: tilt += abs(leftSum - rightSum)
- রিটার্ন leftSum + rightSum + root->data
উদাহরণ কোড
#include <iostream>
using namespace std;
struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int d) : data(d), left(nullptr), right(nullptr) {}
};
int sumNodes(TreeNode* root, int &tiltSum) {
if (!root) return 0;
int lsum = sumNodes(root->left, tiltSum);
int rsum = sumNodes(root->right, tiltSum);
tiltSum += abs(lsum - rsum);
return lsum + rsum + root->data;
}
int findTilt(TreeNode* root) {
int tiltSum = 0;
sumNodes(root, tiltSum);
return tiltSum;
}
int main() {
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(9);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(7);
cout << findTilt(root) << endl; // 15
return 0;
}
আউটপুট
15
