ধরা যাক একটি বাইনারি ট্রি আছে; আমরা এটিকে ইন-প্লেসে লিংকড লিস্টে ফ্ল্যাটেন করব। যদি ট্রি নিচের মতো হয় −
আউটপুট ট্রি হবে −
সমাধানের ধাপগুলো −
prev := null সেট করব
solve() নামে একটি রিকারসিভ ফাংশন সংজ্ঞা করব, যা root ইনপুট হিসেবে নিবে।
যদি root null হয়, তবে রিটার্ন করব
solve(root-এর ডান)
solve(root-এর বাম)
root-এর ডান := prev, root-এর বাম := null
prev := root
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; }else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; }else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class Solution { public: TreeNode* prev = NULL; void flatten(TreeNode* root) { if(!root) return; flatten(root->right); flatten(root->left); root->right = prev; root->left = NULL; prev = root; } }; main(){ vector<int> v = {1,2,5,3,4}; TreeNode *root = make_tree(v); Solution ob; (ob.flatten(root)); TreeNode *ptr = root; while(ptr != NULL && ptr->val != 0){ cout << ptr->val << ", "; ptr = ptr->right; } }
ইনপুট
[1,2,5,3,4]
আউটপুট
1, 2, 3, 4, 5,
